线段树维护 \(c_i\) 表示最小初值使根据题意经过节点表示区间 \([l,r]\) 过程中共减去 \(i\cdot p\)，区间 \([l,r]\) 操作过程中最多减去 \((r-l+1)\cdot p\)。
区间合并就是
，其中 \(x,y\) 的合法条件是，满足初值为 \(tr_{ls,c_x}\) 的最大值即 \(tr_{ls,c_{x+1}}-1\)，在操作完 \(ls\) 表示区间后大于等于 \(tr_{rs,c_y}\)，\(tr_{ls,c_{x+1}}-1+sum_{ls}-x\cdot p \ge tr_{rs,c_y}\) 等价 \(tr_{ls,c_{x+1}}+sum_{ls}-x\cdot p > tr_{rs,c_y}\)。
\(tr_{ls,c_x}\) 即满足左区间减 \(x\cdot p\) 的最小初值，
\(tr_{rs,c_{x+1}}\) 即满足右区间减 \(y\cdot p\) 的最小初值与操作完左区间的值的差值加上满足左区间条件的最小初值 \(tr_{ls,c_x}\) 即 \(tr_{rs,c_y}-(tr_{ls,c_x}+sum_{ls}-x\cdot p)+tr_{ls,c_x}=tr_{rs,c_y}-sum_{ls}+x\cdot p\)。
这样的话时间复杂度接近 \(O(qn^2)\)（？）。
\(tr_{ls,c_{x+1}}-1+sum_{ls}-x\cdot p \ge tr_{rs,c_y}\Leftrightarrow tr_{ls,c_{x+1}}-1 \ge tr_{rs,c_y}-sum_{ls}+x\cdot p\Leftrightarrow \max(tr_{ls,c_x},tr_{rs,c_y}-sum_{ls}+x\cdot p)<tr_{ls,c_x+1}\)，则 \(\max(tr_{ls,c_x},tr_{rs,c_y}-sum_{ls}+x\cdot p)<\max(tr_{ls,c_{x+1}},tr_{rs,c_{y-1}}-sum_{ls}+(x+1)\cdot p)\) 则对于更新 \(c_{x+y},x\) 取最小值时则更新值最小，所以 \(c_{x+y}\) 只用 \(x,y\) 合法且 \(x\) 最小的状态转移，所以对于 \(x,y\) 的枚举范围只是所有 \(y\) 使得 \(x-1,y\) 不合法但 \(x,y\) 合法即可。
貌似不用证明 \(tr_{ls,c_{x+1}}-1+sum_{ls}-x\cdot p\) 具有单调性，因为 \(tr_{rs,c_y}\) 显然具有单调性，那么对于 任意 \(x\) 合法的 \(y\) 必然是一个前缀，而 \(y\) 只用枚举对于 \(x-1\) 不合法，\(x\) 合法的状态，所以只需从 \(x-1\) 第一个不合法的状态往后枚举即可，所以可以用双指针解决。
时间复杂度 \(O(n\log n+m\log^2n)\)。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
#define max(x,y) (x)>(y)?(x):(y)
#define min(x,y) (x)<(y)?(x):(y)
const int N=1e6+5;int a[N];ll p;
inline ll read(){ll x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();return x*f;
}
struct node{int l,r,lf,rt;ll sum;}tr[N<<2];int tot;ll q[N*30];
inline void pushup(int u){int mid=tr[u].l+tr[u].r>>1;tr[u].sum=tr[u<<1].sum+tr[u<<1|1].sum;for(int i=0,j=0;i<=mid-tr[u].l+1;++i)for((j>tr[u].r-mid?--j:0);j<=tr[u].r-mid;++j){if(q[tr[u<<1].lf+i+1]-i*p+tr[u<<1].sum<=q[tr[u<<1|1].lf+j]){--j;break;}q[tr[u].lf+i+j]=max(q[tr[u<<1].lf+i],q[tr[u<<1|1].lf+j]+i*p-tr[u<<1].sum);}
}
void build(int u,int l,int r){tr[u]={l,r,0};tr[u].lf=tot+1;for(int i=0;i<=r-l+3;i++)q[++tot]=1e18;tr[u].rt=tot;q[tr[u].lf]=-1e18;if(l==r){q[tr[u].lf+1]=p-a[l],tr[u].sum=a[l];return;}int mid=l+r>>1;build(u<<1,l,mid),build(u<<1|1,mid+1,r);pushup(u);
}
ll query(int u,int l,int r,ll v){if(tr[u].l<l||tr[u].r>r){int mid=tr[u].l+tr[u].r>>1;if(l<=mid)v=query(u<<1,l,r,v);if(r>mid)v=query(u<<1|1,l,r,v);return v;}return v+tr[u].sum-p*(upper_bound(q+tr[u].lf,q+1+tr[u].rt,v)-q-tr[u].lf-1);
}
int main(){int n,m;ll lst=0;n=read(),m=read(),p=read();for(int i=1;i<=n;++i)a[i]=read();build(1,1,n);//cout<<q[tr[1].lf+n]<<endl;while(m--){int l,r;ll x;l=read()^lst,r=read()^lst,x=read()^lst;lst=query(1,l,r,x);printf("%lld\n",lst);lst=(lst%n+n)%n;}return 0;
}