#include <bits/stdc++.h>
using namespace std;
const long long N = 1000100;
struct node {
  vector<long long> mk;
  long long l, r, len, sum;
} tr[N * 3];
long long n, m, p, a[N];
inline void update(long long k) {
  long long poif = 0;
  tr[k].sum = tr[k << 1].sum + tr[k << 1 | 1].sum;
  for (long long i = 0; i <= tr[k << 1].len; ++i) {
    while (1) {
      if (tr[k << 1].mk[i + 1] - 1 + tr[k << 1].sum - i * p <
          tr[k << 1 | 1].mk[poif]) {
        if (poif) poif--;
        break;
      }
      tr[k].mk[i + poif] =
          min(tr[k].mk[i + poif],
              max(tr[k << 1].mk[i],
                  tr[k << 1 | 1].mk[poif] - tr[k << 1].sum + i * p));
      poif++;
      if (poif > tr[k << 1 | 1].len) {
        poif--;
        break;
      }
    }
  }
}
void build(long long l, long long r, long long k) {
  tr[k].l = l;
  tr[k].r = r;
  tr[k].len = r - l + 1;
  tr[k].mk.push_back(-919198191145140000);
  for (long long i = 1; i <= tr[k].len + 2; ++i)
    tr[k].mk.push_back(919198191145140000);
  if (l == r) {
    tr[k].sum = a[l];
    tr[k].mk[1] = p - a[l];
    return;
  }
  build(l, (l + r >> 1), k << 1);
  build((l + r >> 1) + 1, r, k << 1 | 1);
  update(k);
}
inline long long getans(long long treepos, long long nsum) {
  long long l = 0, r = tr[treepos].len + 1, ans = 0;
  while (l <= r) {
    long long mida = l + r >> 1;
    if (tr[treepos].mk[mida] > nsum)
      ans = mida, r = mida - 1;
    else
      l = mida + 1;
  }
  return ans - 1;
}
long long qsum(long long l, long long r, long long k, long long nval) {
  if (l == tr[k].l && r == tr[k].r) {
    return nval + tr[k].sum - p * getans(k, nval);
  }
  long long mida = tr[k].l + tr[k].r >> 1;
  if (r <= mida) return qsum(l, r, k << 1, nval);
  if (l > mida) return qsum(l, r, k << 1 | 1, nval);
  return qsum(mida + 1, r, k << 1 | 1, qsum(l, mida, k << 1, nval));
}
inline long long read() {
  long long ret = 0, w = 1;
  char ch;
  while ((ch = getchar()) > '9' || ch < '0' && ch != '-')
    ;
  if (ch == '-')
    w = -1;
  else
    ret = ch - '0';
  while ((ch = getchar()) >= '0' && ch <= '9') ret = ret * 10 + ch - '0';
  return ret * w;
}
signed main() {
  n = read();
  m = read();
  p = read();
  for (long long i = 1; i <= n; ++i) a[i] = read();
  build(1, n, 1);
  for (long long i = 1; i <= m; ++i) {
    long long l, r;
    l = read();
    r = read();
    printf("%lld\n", qsum(l, r, 1, 0));
  }
  return 0;
}
