#include <bits/stdc++.h>
using std::max;
using std::min;
const long long inf = 1e18;
const int maxn = 1e6 + 5;
int n, m, p, a[maxn];
long long sum[maxn << 2];
std ::vector<long long> c[maxn << 2];
void pushup(int k, int l, int r, int mid) {
  sum[k] = sum[k << 1] + sum[k << 1 | 1];
  int y = 0;
  for (int x = 0; x <= mid - l + 1; ++x) {
    if (y == r - mid + 1) --y;
    for (; y <= r - mid; ++y) {
      long long nd = c[k << 1][x + 1] - 1 - 1ll * x * p + sum[k << 1];
      if (c[k << 1 | 1][y] > nd) {
        --y;
        break;
      }
      c[k][x + y] =
          min(c[k][x + y],
              max(c[k << 1][x], c[k << 1 | 1][y] + 1ll * x * p - sum[k << 1]));
    }
  }
}
void build(int k, int l, int r) {
  c[k].resize(r - l + 3);
  for (int i = 0; i <= r - l + 2; ++i) c[k][i] = (i ? inf : -inf);
  if (l == r) return sum[k] = a[l], c[k][1] = p - a[l], void();
  int mid = l + r >> 1;
  build(k << 1, l, mid), build(k << 1 | 1, mid + 1, r), pushup(k, l, r, mid);
}
long long getans(int k, int l, int r, int x, int y, long long in) {
  if (l == x && r == y) {
    int pos =
        std ::upper_bound(c[k].begin(), c[k].end(), in) - c[k].begin() - 1;
    return in + sum[k] - 1ll * p * pos;
  }
  int mid = l + r >> 1;
  if (mid < x) return getans(k << 1 | 1, mid + 1, r, x, y, in);
  if (y <= mid) return getans(k << 1, l, mid, x, y, in);
  return getans(k << 1 | 1, mid + 1, r, mid + 1, y,
                getans(k << 1, l, mid, x, mid, in));
}
int main() {
  scanf("%d %d %d", &n, &m, &p);
  for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
  build(1, 1, n);
  while (m--) {
    int l, r;
    scanf("%d %d", &l, &r), printf("%lld\n", getans(1, 1, n, l, r, 0));
  }
  return 0;
}
