#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MAX = 2e5 + 5;
const int LOG = 13;
vector<int> A;
int tri(int n) {
return n * (n + 1) / 2;
}
int getLayer(int n) {
int l = 1, r = n, m, ans;
while (l <= r) {
m = (l + r) >> 1;
if (tri(m) >= n) {
ans = m;
r = --m;
} else {
l = ++m;
}
}
return ans;
}
int kpa(int n, int k) {
if (k == 0) return n;
const int L = getLayer(n);
if (L - k < 1) return -1;
int X = n - tri(L - 1) - 1;
// cout << X << "&&" << A[L - k] << " " << endl;
// int x = max(0LL, min(k, X - A[L - k]));
int x = 0;
for (int i = L; i >= L - k; i--) if (A[i] <= X) X--, n--;
// int x = max(L - k, min(L, (int) (upper_bound(A.begin(), A.end(), X) - A.begin()) - 1)) - L + k;
// int x = min(k, (int) (upper_bound(A.begin() + L - k, A.begin() + L, X) - (A.begin() + L - k)));
return n - tri(L - 1) + tri(L - k - 1) - x;
}
int LCA(int x, int y) {
int a = getLayer(x), b = getLayer(y), nx, ny;
if (a > b) {
swap(a, b);
swap(x, y);
}
y = kpa(y, b - a);
if (x == y) return x;
for (int i = LOG; i >= 0; i--) {
nx = kpa(x, (1 << i)), ny = kpa(y, (1 << i));
// cout << i << " " << nx << " " << ny << endl;
if (nx != ny) x = nx, y = ny;
}
return kpa(x, 1);
}
signed main() {
int N, Q, T, x, y, p = 0;
cin >> N >> Q >> T;
const int MOD = tri(N + 1);
A.resize(N + 2);
for (int i = 1; i <= N; i++) {
cin >> A[i];
A[i] -= tri(i - 1);
}
A[N + 1] = INT_MAX;
cout << endl << endl;
for (int t: A) cout << t << " ";
cout << endl;
while (Q--) {
cin >> x >> y;
if (T) {
x = (x - 1 + p) % MOD + 1;
y = (y - 1 + p) % MOD + 1;
}
cout << (p = LCA(x, y)) << '\n';
// cout << kpa(x, y) << endl;
}
}
