提交情况：很多

得分情况 $\in [97,99]$

T掉的点 $\in \{\#34,\#58,\#60\}$

T掉的时间 $\in (1.00,1.05)sec$

这东西诗人我直接赤。

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
#define ll long long
const int N=1000300,M=N<<2;
const ll inf=1e18+1234567;
#define re register
ll n,m,p;
ll a[N];
ll v[M];
vector<ll>c[M];
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-48;ch=getchar();}
    return x*f;
}
inline void pushup(int u,int l,int r){
    int mid=l+r>>1;
    v[u]=v[mid<<1]+v[mid<<1|1];
    for(re int x=0,y=0;x<=mid-l+1;++x){
        if(y==r-mid+1)y=r-mid;
        for(;y<=r-mid+1;++y){
            if(c[mid<<1|1][y]>c[mid<<1][x+1]-1-x*p+v[mid<<1]){--y;break;}
            c[u][x+y]=min(c[u][x+y],max(c[mid<<1][x],c[mid<<1|1][y]+x*p-v[mid<<1]));
        }
    }
}
inline void build(int u,int l,int r){
    c[u].resize(r-l+3);
    for(re int i=1;i<=r-l+2;++i)
    c[u][i]=inf;
    c[u][0]=-inf;
    if(l==r){
        v[u]=a[l];
        c[u][1]=p-a[l];
        return;
    }
    int mid=l+r>>1;
    build(mid<<1,l,mid);
    build(mid<<1|1,mid+1,r);
    pushup(u,l,r);
}
inline void write(ll x){
    if(x>9)write(x/10);
    putchar(x%10+48);
}
inline void Write(ll x){
    if(x<0)putchar('-'),write(-x);
    else write(x);
}
inline ll query(int u,int l,int r,int L,int R,ll x){
    if(L<=l&&r<=R){
        return x+v[u]-p*(upper_bound(c[u].begin(),c[u].end(),x)-c[u].begin()-1);
    }
    int mid=l+r>>1;
    // cout<<u<<' '<<l<<' '<<r<<' '<<L<<' '<<R<<' '<<endl;
    if(L>mid)return query(mid<<1|1,mid+1,r,L,R,x);
    if(R<=mid)return query(mid<<1,l,mid,L,R,x);
    return query(mid<<1|1,mid+1,r,L,R,query(mid<<1,l,mid,L,R,x));
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    n=read();m=read();p=read();
    for(re int i=1;i<=n;++i)a[i]=read();
    build(1,1,n);
    ll ans=0;
    while(m--){
        ll x=read(),y=read(),d=read();
        ans=(ans%n+n)%n;
        // x^=ans;y^=ans;d^=ans;
        ans=query(1,1,n,x^ans,y^ans,d^ans);
        cout<<ans<<'\n';//加快写也没用，还没你这玩意跑得快/ll
    }
    return 0;
}