#include <bits/stdc++.h>   using namespace std;   char buf[1 << 21], *p1 = buf, *p2 = buf;   int read() {     int w = 0, f = 1;     char c =    ;     while (c <  0  || c >  9 )       c = (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2)                ? EOF                : *p1++),       f = c ==  -  ? -1 : f;     while (c >=  0  && c <=  9 )       w = w * 10 + c - 48,       c = (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2)                ? EOF                : *p1++);     return w * f;   }   int n, m, a[1000005];   long long val[1000005 << 2], mod;   vector<long long> minn[1000005 << 2];   const long long inf = 1e18;   void pushup(int p, int l, int r, int mid) {     int ls = p << 1, rs = p << 1 | 1, it1 = 0, it2 = 0;     while (it1 <= mid - l + 1) {       while (it2 <= r - mid) {         long long L = max(minn[ls][it1], minn[rs][it2] - val[ls] + mod * it1),                   R = it1 == mid - l + 1 ? inf : minn[ls][it1 + 1] - 1;         if (L > R) break;         minn[p][it1 + it2] = min(minn[p][it1 + it2], L), it2++;       }       it2 = max(it2 - 1, 0), it1++;     }     val[p] = val[ls] + val[rs];   }   void build(int p, int l, int r) {     minn[p].resize(r - l + 2);     minn[p][0] = -inf;     for (int i = 1; i <= r - l + 1; i++) minn[p][i] = inf;     if (l == r) {       minn[p][1] = mod - a[l];       val[p] = a[l];       return;     }     int mid = (l + r) >> 1;     build(p << 1, l, mid);     build(p << 1 | 1, mid + 1, r);     pushup(p, l, r, mid);   }   long long query(int p, int x, int y, long long v, int l, int r) {     if (x <= l && r <= y) {       int L = 0, R = r - l + 1, res = 0;       while (L <= R) {         int mid = (L + R) >> 1;         if (minn[p][mid] <= v)           res = mid, L = mid + 1;         else           R = mid - 1;       }       return v + val[p] - mod * res;     }     int mid = (l + r) >> 1;     if (y <= mid) return query(p << 1, x, y, v, l, mid);     if (x > mid) return query(p << 1 | 1, x, y, v, mid + 1, r);     return query(p << 1 | 1, x, y, query(p << 1, x, y, v, l, mid), mid + 1, r);   }   signed main() {     n = read(), m = read(), mod = read();     for (int i = 1; i <= n; i++) a[i] = read();     build(1, 1, n);     int l, r;     while (m--) {       l = read(), r = read();       printf( %lld n , query(1, l, r, 0, 1, n));     }     return 0;   }   