#include <bits/stdc++.h>
using namespace std;
long long n, m, k;
long long read() {
  long long s = 0, f = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    s = s * 10 + ch - '0';
    ch = getchar();
  }
  return s * f;
}
long long mod;
const long long maxn = 1e6 + 10;
long long a[maxn], sum[maxn << 2];
vector<long long> v[maxn << 2];
const long long inf = 1e15;
long long ls(long long x) { return x << 1; }
long long rs(long long x) { return x << 1 | 1; }
void pushup(long long p, long long l, long long r) {
  long long mid = (l + r) >> 1;
  sum[p] = sum[ls(p)] + sum[rs(p)];
  long long nw = 0;
  for (long long i = 0, iend = mid - l + 1; i <= iend; ++i) {
    if (nw == r - mid + 1) --nw;
    for (; nw <= r - mid; ++nw) {
      long long ns = v[ls(p)][i + 1] - 1 - i * mod + sum[ls(p)];
      if (v[rs(p)][nw] > ns) {
        --nw;
        break;
      }
      v[p][i + nw] = min(v[p][i + nw],
                         max(v[ls(p)][i], v[rs(p)][nw] + i * mod - sum[ls(p)]));
    }
  }
}
void build(long long p, long long l, long long r) {
  v[p].resize(r - l + 3);
  for (long long i = 0, iend = r - l + 2; i <= iend; ++i) {
    v[p][i] = inf;
  }
  v[p][0] = -inf;
  if (l == r) {
    sum[p] = a[l];
    v[p][1] = mod - a[l];
    return;
  }
  long long mid = (l + r) >> 1;
  build(ls(p), l, mid);
  build(rs(p), mid + 1, r);
  pushup(p, l, r);
}
long long query(long long p, long long l, long long r, long long nl,
                long long nr, long long w) {
  if (l == nl && r == nr) {
    long long ps = upper_bound(v[p].begin(), v[p].end(), w) - v[p].begin();
    ps--;
    return w + sum[p] - 1ll * ps * mod;
  }
  long long mid = (l + r) >> 1;
  if (mid < nl) return query(rs(p), mid + 1, r, nl, nr, w);
  if (mid >= nr) return query(ls(p), l, mid, nl, nr, w);
  return query(rs(p), mid + 1, r, mid + 1, nr,
               query(ls(p), l, mid, nl, mid, w));
}
signed main() {
  n = read(), m = read(), mod = read();
  for (long long i = 1, iend = n; i <= iend; ++i) a[i] = read();
  build(1, 1, n);
  while (m--) {
    long long l = read(), r = read();
    printf("%lld\n", query(1, 1, n, l, r, 0));
  }
}
