#include<bits/stdc++.h>
#define taskname "A"
using namespace std;
typedef long long ll;
const int lim = 5e5 + 5;
int n, q, a[lim];
ll k;
namespace sub1{
void solve(){
for(int _ = 0; _ < q; _++){
int l, r;
cin >> l >> r;
ll ans = 0, delta = 0;
for(int i = l; i <= r; i++){
if(~i & 1){
delta = max(0LL, delta - a[i]);
}
else if(delta + a[i] < k){
delta += a[i];
}
else{
ans += (a[i] - (k - delta)) / k + 1;
delta = (a[i] - (k - delta)) % k;
}
}
cout << ans << "\n";
}
}
}
namespace sub2{
void solve(){
vector<ll>f(n + 1);
f[0] = 0;
for(int i = 1; i <= n; i++){
f[i] = f[i - 1];
if(i & 1){
f[i] += a[i] >> (k - 1);
}
}
for(int _ = 0; _ < q; _++){
int l, r;
cin >> l >> r;
cout << f[r] - f[l - 1] << "\n";
}
}
}
namespace sub3{
struct Node{
ll benefit[10], remain[10];
};
vector<Node>st;
Node merge(Node a, Node b){
Node c;
for(int delta = 0; delta < k; delta++){
c.benefit[delta] = a.benefit[delta] + b.benefit[a.remain[delta]];
c.remain[delta] = b.remain[a.remain[delta]];
}
return c;
}
void build(int id, int l, int r){
if(l == r){
if(l & 1){
for(int delta = 0; delta < k; delta++){
if(delta + a[l] < k){
st[id].benefit[delta] = 0;
st[id].remain[delta] = delta + a[l];
}
else{
st[id].benefit[delta] = (a[l] - (k - delta)) / k + 1;
st[id].remain[delta] = (a[l] - (k - delta)) % k;
}
}
}
else{
memset(st[id].benefit, 0, sizeof(st[id].benefit));
for(int delta = 0; delta < k; delta++){
st[id].remain[delta] = max(0, delta - a[l]);
}
}
return;
}
int m = (l + r) >> 1;
build(id << 1, l, m);
build(id << 1 | 1, m + 1, r);
st[id] = merge(st[id << 1], st[id << 1 | 1]);
}
ll ans, delta;
void walk(int id, int l, int r, int u, int v){
if(l > v || r < u){
return;
}
if(u <= l && v >= r){
ans += st[id].benefit[delta];
delta = st[id].remain[delta];
return;
}
int m = (l + r) >> 1;
walk(id << 1, l, m, u, v);
walk(id << 1 | 1, m + 1, r, u, v);
}
void solve(){
st.resize(n << 2 | 3);
build(1, 1, n);
for(int _ = 0; _ < q; _++){
int l, r;
cin >> l >> r;
ans = delta = 0;
walk(1, 1, n, l, r);
cout << ans << "\n";
}
}
}
namespace sub456{
ll delta[lim << 2], ans[lim << 2];
vector<int>query_id[lim << 2];
void walk(int id, int l, int r, int u, int v, int qid){
if(l > v || r < u){
return;
}
if(u <= l && v >= r){
query_id[id].push_back(qid);
return;
}
int m = (l + r) >> 1;
walk(id << 1, l, m, u, v, qid);
walk(id << 1 | 1, m + 1, r, u, v, qid);
}
struct Data{
ll l, r, b, benefit;
bool a;
Data(){}
Data(ll _l, ll _r, bool _a, ll _b, ll _benefit) : l(_l), r(_r), a(_a), b(_b), benefit(_benefit) {}
friend bool operator <(const Data a, const Data b){
return a.l < b.l;
}
};
vector<Data>merge(vector<Data>left, vector<Data>right){
vector<Data>ans;
for(Data& cur : left){
if(cur.a){
ll l = cur.l + cur.b, r = cur.r + cur.b, start = cur.l;
for(auto it = prev(upper_bound(right.begin(), right.end(), Data(l, -1, false, -1, -1))); it != right.end() && it->l <= r; it++){
ll nl = it->l, nr = it->r;
if(nl < l){
if(nr <= r){
ans.push_back(Data(start, start + nr - l, it->a, cur.b * it->a + it->b, cur.benefit + it->benefit));
start += nr - l + 1;
}
else{
ans.push_back(Data(start, cur.r, it->a, cur.b * it->a + it->b, cur.benefit + it->benefit));
break;
}
}
else if(nr <= r){
ans.push_back(Data(start, start + nr - nl, it->a, cur.b * it->a + it->b, cur.benefit + it->benefit));
start += nr - nl + 1;
}
else{
ans.push_back(Data(start, cur.r, it->a, cur.b * it->a + it->b, cur.benefit + it->benefit));
break;
}
}
}
else{
auto it = prev(upper_bound(right.begin(), right.end(), Data(cur.b, -1, false, -1, -1)));
ans.push_back(Data(cur.l, cur.r, false, cur.b * it->a + it->b, cur.benefit + it->benefit));
}
}
return ans;
}
vector<Data>build(int id, int l, int r){
vector<Data>ret;
if(l == r){
if(l & 1){
if(a[l] % k == 0){
ret.push_back(Data(0, k - 1, true, 0, a[l] / k));
}
else{
ret.push_back(Data(0, k - a[l] % k - 1, true, a[l] % k, a[l] / k));
ret.push_back(Data(k - a[l] % k, k - 1, true, -(k - a[l] % k), a[l] / k + 1));
}
}
else if(a[l] >= k - 1){
ret.push_back(Data(0, k - 1, false, 0, 0));
}
else{
ret.push_back(Data(0, a[l], false, 0, 0));
ret.push_back(Data(a[l] + 1, k - 1, true, -a[l], 0));
}
}
else{
int m = (l + r) >> 1;
vector<Data>left = build(id << 1, l, m), right = build(id << 1 | 1, m + 1, r);
ret = merge(left, right);
}
for(int& qid : query_id[id]){
auto it = prev(upper_bound(ret.begin(), ret.end(), Data(delta[qid], -1, false, -1, -1)));
ans[qid] += it->benefit;
delta[qid] = delta[qid] * it->a + it->b;
}
return ret;
}
void solve(){
memset(delta, 0, sizeof(delta));
memset(ans, 0, sizeof(ans));
for(int i = 1; i <= q; i++){
int l, r;
cin >> l >> r;
walk(1, 1, n, l, r, i);
}
build(1, 1, n);
for(int i = 1; i <= q; i++){
cout << ans[i] << "\n";
}
}
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
if(fopen(taskname".inp", "r")){
freopen(taskname".inp", "r", stdin);
}
cin >> n >> q >> k;
for(int i = 1; i <= n; i++){
cin >> a[i];
}
if(q <= 10){
sub1::solve();
}
else if(k <= 2){
sub2::solve();
}
else if(k <= 10){
sub3::solve();
}
else{
sub456::solve();
}
}
