#include <bits/stdc++.h>
using namespace std;
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 (m * (m + 1) / 2 >= 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;
const int X = n - tri(L - 1) - 1;
int x = (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));
if (nx != ny) x = nx, y = ny;
}
return kpa(x, 1);
}
int 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;
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';
}
}
