#include <bits/stdc++.h>
using namespace std;
const long long inf = 0x3f3f3f3f3f3f3f3f;
long long n, m, mod, a[1000010];
inline long long max(long long x, long long y) { return (x > y ? x : y); }
inline long long min(long long x, long long y) { return (x < y ? x : y); }
struct Segment_Tree {
  vector<long long> T[1000010 << 2];
  long long bas[1000010 << 2], len[1000010 << 2];
  inline void pushup(long long x) {
    bas[x] = bas[(x << 1)] + bas[(x << 1 | 1)];
    register long long i = 0, j = 0;
    for (; i <= len[(x << 1)]; ++i) {
      if (j) --j;
      for (; j <= len[(x << 1 | 1)]; ++j) {
        if (T[(x << 1)][i + 1] - i * mod + bas[(x << 1)] <=
            T[(x << 1 | 1)][j]) {
          if (j) --j;
          break;
        }
        T[x][i + j] = min(
            T[x][i + j],
            max(T[(x << 1)][i], T[(x << 1 | 1)][j] + i * mod - bas[(x << 1)]));
      }
    }
    return;
  }
  inline void build(long long x, long long l, long long r) {
    long long mid = (l + r) >> 1;
    len[x] = r - l + 1;
    T[x].resize(r - l + 3);
    for (register long long i = 0; i < r - l + 3; ++i) T[x][i] = inf;
    if (l == r) {
      T[x][0] = -inf;
      T[x][1] = -a[l] + mod;
      T[x][2] = inf;
      bas[x] = a[l];
      return;
    }
    build((x << 1), l, mid);
    build((x << 1 | 1), mid + 1, r);
    pushup(x);
    return;
  }
  inline void query(long long x, long long l, long long r, long long lx,
                    long long rx, long long &ans) {
    if (lx <= l && r <= rx) {
      long long L = 0, R = len[x] + 1;
      while (L < R) {
        long long mid = (L + R + 1) >> 1;
        if (T[x][mid] <= ans)
          L = mid;
        else
          R = mid - 1;
      }
      ans = ans + bas[x] - L * mod;
      return;
    }
    long long mid = (l + r) >> 1;
    if (lx <= mid) query((x << 1), l, mid, lx, rx, ans);
    if (rx > mid) query((x << 1 | 1), mid + 1, r, lx, rx, ans);
    return;
  }
} tree;
inline long long read() {
  long long x = 0;
  char c = getchar();
  bool y = 1;
  for (; c < '0' || c > '9'; c = getchar())
    if (c == '-') y = 0;
  for (; c >= '0' && c <= '9'; c = getchar()) x = (x << 1) + (x << 3) + c - 48;
  if (y) return x;
  return -x;
}
inline void Input() {
  n = read(), m = read(), mod = read();
  for (register long long i = 1; i <= n; ++i) a[i] = read();
  tree.build(1, 1, n);
  return;
}
inline void solve() {
  for (register long long i = 1; i <= m; ++i) {
    long long l = read(), r = read(), ans = 0;
    tree.query(1, 1, n, l, r, ans);
    printf("%lld\n", ans);
  }
  return;
}
signed main() {
  Input();
  solve();
  return 0;
}
