#include <iostream> #include <bits/stdc++.h> #include <climits> #include <stdio.h> using namespace std; const int N = 1e6 + 5; int n, m, p, a[N], sum[N]; inline find_x(int L, int R) { int l = L, r = R; while (l < r) { int mid = (l + r) >> 1; if (a[mid] - a[L - 1] > 0) { l = mid; } else { r = mid - 1; } } return l; } signed main() { cin >> n >> m >> p; int f1 = 1, f2 = 1, f3 = 1, f4 = 1; for (int i = 1; i <= n; ++ i ) { cin >> a[i]; if (a[i] < 0 || a[i] >= p) { f1 = 0; } if (a[i] < p) { f2 = 0; } if (a[i] < a[i - 1] && i - 1 != 0) { f3 = 0; } if (a[i] > a[i - 1] && i - 1 != 0) { f4 = 0; } sum[i] = sum[i - 1] + a[i]; } if (f1 == 1) { for (int i = 1; i <= m; ++ i) { int l, r; cin >> l >> r; int ans = sum[r] - sum[l - 1]; cout << ans - (ans / p * p) << '\n'; } } else if (f2 == 1) { for (int i = 1; i <= m; ++ i) { int l, r; cin >> l >> r; int ans = sum[r] - sum[l - 1]; cout << ans - (r - l + 1) * p << '\n'; } } else if (f3 == 1) { int f = 0; for (int i = 1; i <= n; ++ i) { if (a[i] >= p) { f = i - 1; break; } } for (int i = 1; i <= m; ++ i) { int l, r; cin >> l >> r; if (l <= f && f < r) { int ans1 = sum[f] - sum[l - 1]; int ans2 = sum[r] - sum[f]; int tmp = ans1 / p + p; if (ans1 < 0) { int k = upper_bound(sum + f + 1 + 1, sum + r + 1, -ans1 + sum[f] + p) - sum - 1; cout << ans1 + ans2 - (r - k) * p << '\n'; continue; } cout << ans1 - (ans1 / p * p) + ans2 - (r - f) * p << '\n'; } else if (f >= r) { int ans = sum[r] - sum[l - 1]; int tmp = ans / p * p; if (tmp < 0) { tmp = 0; } cout << ans - (tmp * p) << '\n'; } else if (f < l) { int ans = sum[r] - sum[l - 1]; cout << ans - (r - l + 1) * p << '\n'; } } } else if (f4 == 1) { int f = 0, f1 = 0; for (int i = 1; i <= n; ++ i) { if (a[i] < p && f == 0) { f = i - 1; } if (a[i] < 0 && f1 == 0) { f1 = i - 1; } } for (int i = 1; i <= m; ++ i) { int l, r; cin >> l >> r; if (l <= f && f < r) { int ans1 = sum[f] - sum[l - 1] - (f - l + 1) * p; int k = find_x(f + 1, r); int ans2 = sum[k] - sum[f]; if (ans2 + ans1 <= 0) { k -= 1; } ans2 = sum[k] - sum[f]; cout << ans1 + ans2 - min((ans1 + ans2) / p, k - f) * p + sum[r] - sum[k] << '\n'; } else if (f < l && l <= f1 && f1 <= r) { int ans1 = sum[f1] - sum[l - 1]; int ans2 = sum[r] - sum[f1]; cout << ans1 - (ans1 / p * p) + ans2 << '\n'; } else if (f < l && f1 < l) { int ans1 = sum[r] - sum[l - 1]; cout << ans1 << '\n'; } else if (f < l && f1 > r) { int ans1 = sum[r] - sum[l - 1]; cout << ans1 - (ans1 / p * p) << '\n'; } else if (f >= r) { int ans = sum[r] - sum[l - 1]; cout << ans - (r - l + 1) * p << '\n'; } } } } /* 4 5 6 -12 -5 -3 17 2 3 1 3 1 2 2 4 4 4 */