题解：CF1172F Nauuo and Bug

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define debug(x) cerr<<#x<<':'<<x<<endl
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
using namespace std;
const int N=1e6+5;
int n,m,mod;
int a[N];
int id[N];
int val[N],tag[N],fa[N],lc[N],rc[N],key[N];
int tot,root;
int ans[N];
vector<int> L[N],R[N];
mt19937 rnd(time(0));
inline int new_node(int x){
    tot++;
    val[tot]=x,key[tot]=rnd();
    return tot;
}
inline void push_up(int p){
    fa[p]=0;
    if(lc[p]) fa[lc[p]]=p;
    if(rc[p]) fa[rc[p]]=p;
}
inline void push_down(int p){
    if(!tag[p]) return;
    if(lc[p]) val[lc[p]]+=tag[p],tag[lc[p]]+=tag[p];
    if(rc[p]) val[rc[p]]+=tag[p],tag[rc[p]]+=tag[p];
    tag[p]=0;
}
void split(int p,int k,int &x,int &y){
    if(!p) return x=y=0,void();
    push_down(p);
    if(val[p]<=k){
        x=p;
        split(rc[p],k,rc[x],y);
        push_up(x);
    }
    else{
        y=p;
        split(lc[p],k,x,lc[y]);
        push_up(y);
    }
}
int merge(int x,int y){
    if(!x||!y) return x|y;
    push_down(x),push_down(y);
    if(key[x]>key[y]){
        rc[x]=merge(rc[x],y);
        push_up(x);
        return x;
    }
    else{
        lc[y]=merge(x,lc[y]);
        push_up(y);
        return y;
    }
}
inline int ins(int x){
    int a,b;
    split(root,x,a,b);
    int p=new_node(x);
    root=merge(a,merge(p,b));
    return p;
}
int mi(int x){
    while(lc[x]) push_down(x),x=lc[x];
    return val[x];
}
inline void change(int x){
    int a,b;
    split(root,mod-x-1,a,b);
    if(a) val[a]+=x,tag[a]+=x;
    if(b) val[b]+=x-mod,tag[b]+=x-mod;
    root=0;
    if(mi(a)>mi(b)) swap(a,b);
    while(b){
        int u,v;
        split(a,mi(b),u,v);
        root=merge(root,u);
        a=v,swap(a,b);
    }
    root=merge(root,a);
}
inline int query(int x){
    int res=val[x];
    while(fa[x]) x=fa[x],res+=tag[x];
    return res;
}
signed main(){
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    IOS;
    cin>>n>>m>>mod;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1,l,r;i<=m;i++){
        cin>>l>>r;
        L[l].push_back(i),R[r].push_back(i);
    }
    for(int i=1;i<=n;i++){
        for(int x:L[i]) id[x]=ins(0);
        change(a[i]);
        for(int x:R[i]) ans[x]=query(id[x]);
    }
    for(int i=1;i<=m;i++) cout<<ans[i]<<endl;
    return 0;
}