#include<bits/stdc++.h> #define int long long using namespace std; const int N = 1e6+2; int n,m,p; int a[N],s[N]; bool k1 = 1,k2 = 1,k3 = 1,k4 = 1; int find1(int l,int r) { int ans = -1; int L = l; while(l <= r) { int mid = (l+r)>>1; if(s[mid]-s[L-1] < 0) l = mid+1; else { ans = mid; r = mid-1; } } return ans; } int find2(int l,int r) { int ans = -1; while(l <= r) { int mid = (l+r)>>1; if(a[mid] < p) l = mid+1; else { ans = mid; r = mid-1; } } return ans; } int find3(int l,int r) { int ans = -1; int L = l; while(l <= r) { int mid = (l+r)>>1; if(s[mid]-s[L-1]-p*(mid-L+1) >= p) l = mid+1; else { ans = mid; r = mid-1; } } return ans; } int find4(int l,int r) { int ans = -1; while(l <= r) { int mid = (l+r)>>1; if(a[mid] > 0) l = mid+1; else { ans = mid; r = mid-1; } } return ans; } signed main() { scanf("%lld%lld%lld",&n,&m,&p); for(int i = 1;i <= n;i++) { scanf("%lld",&a[i]); s[i] = s[i-1]+a[i]; if(a[i] < 0 || a[i] >= p) k1 = 0; if(a[i] < p) k2 = 0; if(i > 1 && a[i] < a[i-1]) k3 = 0; if(i > 1 && a[i] > a[i-1]) k4 = 0; } if(k1) { for(int i = 1;i <= m;i++) { int l,r; scanf("%lld%lld",&l,&r); printf("%lld\n",(s[r]-s[l-1])%p); } } else if(k2) { for(int i = 1;i <= m;i++) { int l,r; scanf("%lld%lld",&l,&r); printf("%lld\n",(s[r]-s[l-1])-(r-l+1)*p); } } else if(k3) { for(int i = 1;i <= m;i++) { int l,r; scanf("%lld%lld",&l,&r); int pos = find1(l,r); if(pos == -1) { printf("%lld\n",s[r]-s[l-1]); continue; } int ans = s[pos]-s[l-1]; if(ans >= p) ans -= p; if(pos == r) { printf("%lld\n",ans); continue; } if(s[pos+1] >= p) { printf("%lld\n",ans-(r-pos)*p); continue; } int nxt = find2(pos+1,r); if(nxt == -1) { printf("%lld\n",(ans+s[r]-s[pos])%p); continue; } else { ans = (ans+s[nxt-1]-s[pos])%p; ans = (ans+(s[r]-s[nxt-1])-(r-nxt+1)*p); printf("%lld\n",ans); } } } else if(k4) { for(int i = 1;i <= m;i++) { int l,r; scanf("%lld%lld",&l,&r); int pos = find3(l,r); if(pos == -1) { printf("%lld\n",(s[r]-s[l-1])-p*(r-l+1)); continue; } int ans = (s[pos]-s[l-1])-p*(pos-l+1); if(pos == r) { printf("%lld\n",ans); continue; } int nxt = find2(pos+1,r); if(nxt == -1) { printf("%lld\n",(ans+s[r]-s[pos])%p); } else { ans = (ans+s[nxt-1]-s[pos])%p; ans = ans+(s[r]-s[nxt]); printf("%lld\n",ans); } } } return 0; }