#include <bits/stdc++.h>
using namespace std;
const long long inf = 5e16;
const int N = 1.1e6;
struct func {
  long long r, b;
  inline long long operator()(long long x) { return x + b; }
  inline bool operator<(const func& rhs) const { return r < rhs.r; }
};
func* d[N << 1];
int n, m, md, sz[N << 1];
void merge(func*& h, func* F, func* g, int& szh, const int& szf,
           const int& szg) {
  static func sta[N << 1], f[N << 1];
  int top = 0;
  sta[0].b = inf;
  for (int i = 0; i < szf; ++i) f[i + 1] = F[i];
  f[0].r = -inf;
  for (int i = 1, it = 0; i <= szf;) {
    const long long L = max(-inf, f[i](f[i - 1].r + 1)),
                    R = min(inf, f[i](f[i].r));
    while (it < szg && L > g[it].r) ++it;
    if (R <= g[it].r) {
      long long b = f[i].b + g[it].b;
      if (sta[top].b != b)
        sta[++top] = (func){f[i].r, b};
      else
        sta[top].r = f[i].r;
      ++i;
    } else {
      const long long mid = g[it].r - f[i].b;
      long long b = f[i].b + g[it].b;
      if (sta[top].b != b)
        sta[++top] = (func){mid, f[i].b + g[it].b};
      else
        sta[top].r = mid;
      f[i - 1].r = mid;
    }
    it -= !!it;
  }
  h = new func[szh = top];
  for (int i = 1; i <= top; ++i) h[i - 1] = sta[i];
}
void build(int l, int r, int o) {
  if (l == r) {
    int x;
    cin >> x;
    d[o] = new func[sz[o] = 2];
    d[o][0] = (func){md - x - 1, x}, d[o][1] = (func){inf, x - md};
  } else {
    const int mid = l + r >> 1;
    build(l, mid, o << 1), build(mid + 1, r, o << 1 | 1);
    merge(d[o], d[o << 1], d[o << 1 | 1], sz[o], sz[o << 1], sz[o << 1 | 1]);
  }
}
void trans(int l, int r, int o, const int& L, const int& R, long long& ans) {
  if (L <= l && r <= R) {
    ans = (*(lower_bound(d[o], d[o] + sz[o], (func){ans})))(ans);
  } else {
    const int mid = l + r >> 1;
    if (L <= mid) trans(l, mid, o << 1, L, R, ans);
    if (mid < R) trans(mid + 1, r, o << 1 | 1, L, R, ans);
  }
}
int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cin >> n >> m >> md;
  build(1, n, 1);
  while (m--) {
    long long ans = 0;
    int l, r;
    cin >> l >> r;
    trans(1, n, 1, l, r, ans);
    cout << ans << '\n';
  }
  return 0;
}
