#include <bits/stdc++.h>
using namespace std;
template <typename T>
void rd(T& x) {
  int f = 0, c;
  while (!isdigit(c = getchar())) f ^= !(c ^ 45);
  x = (c & 15);
  while (isdigit(c = getchar())) x = x * 10 + (c & 15);
  if (f) x = -x;
}
template <typename T>
void pt(T x, int c = -1) {
  if (x < 0) putchar('-'), x = -x;
  if (x > 9) pt(x / 10);
  putchar(x % 10 + 48);
  if (c != -1) putchar(c);
}
const int N = 1000005;
const long long INFLL = 0X3F3F3F3F3F3F3F3FLL;
int n, m, p, a[N];
long long sum[N * 4];
vector<long long> v[N * 4];
void upd(int k1, int sz) {
  sum[k1] = sum[k1 * 2] + sum[k1 * 2 + 1];
  int lsz = (sz + 1) >> 1;
  int rsz = sz >> 1;
  v[k1].assign(sz + 2, INFLL);
  int j = 0;
  for (int i = (0); i <= (lsz); ++i) {
    if (j > rsz) --j;
    for (; j <= rsz; ++j) {
      long long tem = v[k1 * 2 + 1][j] + 1LL * i * p - sum[k1 * 2];
      long long w = v[k1 * 2][i + 1] - 1 - 1LL * i * p + sum[k1 * 2];
      if (w < v[k1 * 2 + 1][j]) {
        if (j) --j;
        break;
      }
      v[k1][i + j] = min(v[k1][i + j], max(v[k1 * 2][i], tem));
    }
  }
}
void bud(int k1, int k2, int k3) {
  ((void)0);
  if (k2 == k3) {
    v[k1].push_back(~INFLL);
    v[k1].push_back(p - a[k2]);
    v[k1].push_back(INFLL);
    sum[k1] = a[k2];
    return;
  }
  int mid = (k2 + k3) >> 1;
  bud(k1 * 2, k2, mid), bud(k1 * 2 + 1, mid + 1, k3);
  upd(k1, k3 - k2 + 1);
}
long long qry(int k1, int k2, int k3, int k4, int k5, long long k6) {
  ((void)0);
  if (k2 > k5 || k3 < k4) return k6;
  if (k4 <= k2 && k3 <= k5) {
    long long pos =
        upper_bound(v[k1].begin(), v[k1].end(), k6) - v[k1].begin() - 1;
    return k6 - p * pos + sum[k1];
  }
  int mid = (k2 + k3) >> 1;
  return qry(k1 * 2 + 1, mid + 1, k3, k4, k5, qry(k1 * 2, k2, mid, k4, k5, k6));
}
signed main() {
  rd(n), rd(m), rd(p);
  for (int i = (1); i <= (n); ++i) rd(a[i]);
  bud(1, 1, n);
  for (int i = (1); i <= (m); ++i) {
    int l, r;
    rd(l), rd(r);
    pt(qry(1, 1, n, l, r, 0), '\n');
  }
  return 0;
}
