#include <bits/stdc++.h>
using namespace std;
const int N = 1000007;
vector<long long> c[N * 4];
long long tr[N * 4], a[N], k;
int n, m, le[N * 4];
void mrg(int i) {
  tr[i] = tr[(i << 1)] + tr[(i << 1 | 1)];
  int y = 0;
  for (int x = (0); x <= (le[(i << 1)]); x++) {
    for (int j = (min(le[(i << 1 | 1)], y)); j <= (le[(i << 1 | 1)]); j++) {
      y = j + 1;
      if (c[(i << 1)][x + 1] - 1 - x * k + tr[(i << 1)] < c[(i << 1 | 1)][j]) {
        y = max(y - 2, 0);
        break;
      }
      c[i][x + j] =
          min(c[i][x + j],
              max(c[(i << 1)][x], c[(i << 1 | 1)][j] + x * k - tr[(i << 1)]));
    }
  }
}
void bld(int i, int l, int r) {
  le[i] = r - l + 1;
  for (int j = (1); j <= (le[i] + 2); j++) c[i].push_back(1e18);
  c[i][0] = -1e18;
  if (l == r) {
    c[i][1] = k - a[l];
    tr[i] = a[l];
    return;
  }
  bld((i << 1), l, ((l + r) >> 1));
  bld((i << 1 | 1), ((l + r) >> 1) + 1, r);
  mrg(i);
}
long long qry(int i, int l, int r, int s, int t, long long w) {
  if (s <= l && r <= t) {
    long long po =
        (upper_bound(c[i].begin(), c[i].end(), w) - c[i].begin() - 1);
    return w + tr[i] - k * po;
  }
  if (t <= ((l + r) >> 1)) return qry((i << 1), l, ((l + r) >> 1), s, t, w);
  if (s > ((l + r) >> 1))
    return qry((i << 1 | 1), ((l + r) >> 1) + 1, r, s, t, w);
  return qry((i << 1 | 1), ((l + r) >> 1) + 1, r, s, t,
             qry((i << 1), l, ((l + r) >> 1), s, t, w));
}
int main() {
  scanf("%d%d%lld", &n, &m, &k);
  for (int i = (1); i <= (n); i++) scanf("%lld", &a[i]);
  bld(1, 1, n);
  for (int i = (1); i <= (m); i++) {
    int x, y;
    scanf("%d%d", &x, &y);
    printf("%lld\n", qry(1, 1, n, x, y, 0));
  }
}
