#include <bits/stdc++.h>
using namespace std;
template <class T>
inline void chkmax(T &a, T b) {
  if (a < b) a = b;
}
template <class T>
inline void chkmin(T &a, T b) {
  if (a > b) a = b;
}
inline int read() {
  int sum = 0, p = 1;
  char ch = getchar();
  while (!(('0' <= ch && ch <= '9') || ch == '-')) ch = getchar();
  if (ch == '-') p = -1, ch = getchar();
  while ('0' <= ch && ch <= '9') sum = sum * 10 + ch - 48, ch = getchar();
  return sum * p;
}
const int maxn = 1e6 + 20;
const long long inf = 1ll << 60;
int n, m, p;
int a[maxn];
struct node {
  vector<long long> R, B;
  inline void Merge(node a, node b) {
    int n = ((int)a.R.size()) - 1, m = ((int)b.R.size()) - 1, j = 0;
    long long lst = -inf;
    for (int i = (0), _end_ = (n); i <= _end_; i++) {
      while (j <= m) {
        long long x = b.R[j] - a.B[i];
        if (x >= lst) {
          R.push_back(min(x, a.R[i]));
          B.push_back(a.B[i] + b.B[j]);
        }
        if (x >= a.R[i]) break;
        j++;
      }
      if (j) j--;
      lst = a.R[i];
    }
    vector<long long> nR, nB;
    nR.push_back(R.front());
    nB.push_back(B.front());
    int t = 0;
    for (int i = (1), _end_ = (((int)R.size()) - 1); i <= _end_; i++)
      if (B[i] == nB.back())
        nR[t] = R[i];
      else
        nR.push_back(R[i]), nB.push_back(B[i]), ++t;
    R = nR;
    B = nB;
  }
};
node c[(1 << 21) + 20];
void make_tree(int o, int l, int r) {
  if (l == r)
    return c[o].R = {p - a[l] - 1, inf}, c[o].B = {a[l], a[l] - p}, void();
  int mid = l + r >> 1;
  make_tree((o << 1), l, mid);
  make_tree((o << 1 | 1), mid + 1, r);
  c[o].Merge(c[(o << 1)], c[(o << 1 | 1)]);
}
inline void init() {
  n = read();
  m = read();
  p = read();
  for (int i = (1), _end_ = (n); i <= _end_; i++) a[i] = read();
  make_tree(1, 1, n);
}
void query(int ql, int qr, long long &x, int o, int l, int r) {
  if (ql <= l && r <= qr) {
    int t = lower_bound(c[o].R.begin(), c[o].R.end(), x) - c[o].R.begin();
    x += c[o].B[t];
    return;
  }
  int mid = l + r >> 1;
  if (ql <= mid) query(ql, qr, x, (o << 1), l, mid);
  if (qr > mid) query(ql, qr, x, (o << 1 | 1), mid + 1, r);
}
inline void doing() {
  for (int i = (1), _end_ = (m); i <= _end_; i++) {
    int l = read(), r = read();
    long long ans = 0;
    query(l, r, ans, 1, 1, n);
    printf("%lld\n", ans);
  }
}
int main() {
  init();
  doing();
  return 0;
}
