#include <bits/stdc++.h>
using namespace std;
using namespace std::chrono;
const long long int big = 2.19e17 + 1;
const long double pai = 3.141592653589793238462643383279502884197;
const long double eps = 1e-15;
template <class T, class U>
bool mineq(T& a, U b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
}
template <class T, class U>
bool maxeq(T& a, U b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}
long long int gcd(long long int a, long long int b) {
  if (a % b == 0) {
    return b;
  } else
    return gcd(b, a % b);
}
long long int lcm(long long int a, long long int b) {
  if (a == 0) {
    return b;
  }
  return a / gcd(a, b) * b;
}
template <class T>
void SO(T& ve) {
  sort(ve.begin(), ve.end());
}
template <class T>
void REV(T& ve) {
  reverse(ve.begin(), ve.end());
}
template <class T>
long long int LBI(vector<T>& ar, T in) {
  return lower_bound(ar.begin(), ar.end(), in) - ar.begin();
}
template <class T>
long long int UBI(vector<T>& ar, T in) {
  return upper_bound(ar.begin(), ar.end(), in) - ar.begin();
}
int main(void) {
  cin.tie(0);
  ios::sync_with_stdio(false);
  static vector<long long int> ta[2097152];
  static long long int wa[2097152];
  long long int n, m, mod, i;
  cin >> n >> m >> mod;
  for (i = 1 << 20; i < n + (1 << 20); i++) {
    cin >> wa[i];
    ta[i].push_back(mod);
  }
  for (i = (1 << 20) - 1; i > 0; i--) {
    int L = i + i, R = i + i + 1;
    wa[i] = wa[L] + wa[R];
    int Lb = 0, Rb = 0;
    long long int pe = 0, sai = -big;
    while (Lb < ta[L].size() || Rb < ta[R].size()) {
      long long int Lx, Rx;
      if (Lb < ta[L].size()) {
        Lx = max(ta[L][Lb] + wa[R], sai + mod * (Lb + 1));
      } else {
        Lx = big;
      }
      if (Rb < ta[R].size()) {
        Rx = ta[R][Rb] + pe;
      } else {
        Rx = big;
      }
      if (Lx < Rx) {
        ta[i].push_back(Lx);
        pe += mod;
        Lb++;
      } else {
        ta[i].push_back(Rx);
        sai = ta[R][Rb];
        Rb++;
      }
    }
  }
  while (m--) {
    long long int L, R;
    cin >> L >> R;
    L += (1 << 20) - 2;
    R += (1 << 20);
    long long int ans = 0;
    deque<int> mae;
    deque<int> ato;
    while (L + 1 < R) {
      if (L % 2 == 0) {
        mae.push_back(L + 1);
      }
      if (R % 2 == 1) {
        ato.push_front(R - 1);
      }
      L /= 2;
      R /= 2;
    }
    for (auto it : mae) {
      ans += wa[it];
      ans -= mod * UBI(ta[it], ans);
    }
    for (auto it : ato) {
      ans += wa[it];
      ans -= mod * UBI(ta[it], ans);
    }
    cout << ans << endl;
  }
  return 0;
}
