#include <bits/stdc++.h>
using namespace std;
bool M1;
#define task "task"
#define bit(x, i) ((x >> i) & 1)
// https://trap.jp/post/1224/
#define FOR1(i, a, b) for(int i = (a), _b = (b); i <= _b; i ++)
#define FOR2(i, a, b, c) for(int i = (a), _b = (b); i <= _b; i += c)
#define FORD1(i, a, b) for(int i = (a), _b = (b); i >= _b; i --)
#define FORD2(i, a, b, c) for(int i = (a), _b = (b); i >= _b; i -= c)
#define overload4(a, b, c, d, name, ...) name
#define FOR(...) overload4(__VA_ARGS__, FOR2, FOR1)(__VA_ARGS__)
#define FORD(...) overload4(__VA_ARGS__, FORD2, FORD1)(__VA_ARGS__)
#define pb emplace_back
#define pf emplace_front
#define ins emplace
#define mp make_pair
#define fi first
#define se second
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;
// mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
// ll rand(ll l, ll r) { assert(l <= r); return uniform_int_distribution<ll>(l, r)(rd); }
const int N = 2e5 + 5;
const ll inf = 1e18;
const int mod = 1e9 + 7;
const int base = 31;
int n, q, t, a[N];
ll bottom[N];
int root[N];
struct PersistentSegmentTree{
#define lc st[id].l
#define rc st[id].r
int n;
struct Node{
int id, sz, l, r;
} st[(17 * 3 + 4) * N];
int cur = 0;
void init(int _n){
n = _n;
}
int update(int pre, int l, int r, int pos, int val){
int id = ++ cur;
st[id] = st[pre];
if(l == r){
st[id].sz = (val > 0);
st[id].id = val;
return id;
}
int mid = l + r >> 1;
if(pos <= mid){
rc = st[pre].r;
lc = update(st[pre].l, l, mid, pos, val);
}
else{
lc = st[pre].l;
rc = update(st[pre].r, mid + 1, r, pos, val);
}
st[id].sz = st[lc].sz + st[rc].sz;
return id;
}
pii query(int id, int l, int r, int k){
if(l == r) return {l, st[id].id};
int mid = l + r >> 1;
int cnt = st[lc].sz;
if(k > cnt) return query(rc, mid + 1, r, k - cnt);
else return query(lc, l, mid, k);
}
void upd(int v, int pos, int val){
root[v] = update(root[v], 1, n, pos, val);
}
pii get(int v, int k){
return query(root[v], 1, n, k);
}
} pst;
int ver = 1;
const int M = 2 * N;
int h[M], par[M][20];
vector<int> g[M];
void dfs(int u, int p){
par[u][0] = p;
FOR(i, 1, 17) par[u][i] = par[par[u][i - 1]][i - 1];
for(int v : g[u]) if(v != p){
h[v] = h[u] + 1;
dfs(v, u);
}
}
int lca(int u, int v){
if(h[u] < h[v]) swap(u, v);
FORD(i, 17, 0) if(h[par[u][i]] >= h[v]) u = par[u][i];
if(u == v) return u;
FORD(i, 17, 0) if(par[u][i] != par[v][i]) u = par[u][i], v = par[v][i];
return par[u][0];
}
int getfl(ll x){
int i = sqrt(2 * x);
while(i * (i + 1) / 2 < x) ++i;
while(i * (i - 1) / 2 >= x) --i;
return i;
}
ll calc(ll x, ll y){
int idx = getfl(x), idy = getfl(y);
int posx = x - 1ll * idx * (idx - 1) / 2, posy = y - 1ll * idy * (idy - 1) / 2;
int compx = pst.get(idx, posx).se, comy = pst.get(idy, posy).se;
int p = lca(compx, comy);
return min({x, y, bottom[p]});
}
void solve(){
cin>>n>>q>>t;
FOR(i, 1, n) cin>>a[i];
pst.init(n + 1);
FOR(i, 1, n + 1){
bottom[i] = 1ll * n * (n + 1) / 2 + i;
pst.upd(n + 1, i, i);
}
int comp = n + 1;
FORD(i, n, 1){
int idx = 1ll * a[i] - i * (i - 1) / 2;
pii l = pst.get(i + 1, idx), r = pst.get(i + 1, idx + 1);
bottom[++comp] = a[i];
g[comp].pb(l.se);
g[l.se].pb(comp);
g[comp].pb(r.se);
g[r.se].pb(comp);
root[i] = pst.update(root[i + 1], 1, n + 1, l.fi, comp);
root[i] = pst.update(root[i], 1, n + 1, r.fi, 0);
}
dfs(comp, 0);
ll ans = 0;
while(q --){
ll x, y; cin>>x>>y;
x = (x - 1 + 1ll * t * ans) % (1ll * (n + 1) * (n + 2) / 2) + 1;
y = (y - 1 + 1ll * t * ans) % (1ll * (n + 1) * (n + 2) / 2) + 1;
ans = calc(x, y);
cout<<ans<<'\n';
}
}
bool M2;
signed main(){
ios::sync_with_stdio(false);
cin.tie(NULL);
if(fopen(task".inp", "r")){
freopen(task".inp", "r", stdin);
freopen(task".out", "w", stdout);
}
int tc = 1;
// cin>>tc;
while(tc --) solve();
cerr << "\nMemory: " << abs(&M2-&M1)/1024.0/1024 << " Mb\n";
cerr << "\nTime: " << 1.0 * clock() / CLOCKS_PER_SEC << " ms\n";
return 0;
}
