Day 21。
容易发现最优解里一定存在一种方案，为「一开始停留一段时间，然后一直往下一个取」的形式。通过调整容易证明。
断环成链，直接列出式子：
\[\text{ans}=\min\limits_{n\le i<2n}\max\limits_{i-n< j\le i}a_j-j+i
\]
令 \(t_i=a_i-i(1\le i\le 2n)\)，然后让 \(i\) 平移 \(n-1\) 位，化简后得：
\[\text{ans}=(n-1)+\min\limits_{1\le i\le n}\left(i+\max\limits_{i\le j\le 2n}a_j\right)
\]
相当于对每个 \(i\)，求出其后缀最大值 \(a_j\)。反过来，考虑每个 \(j\)，其作为 \(i\) 的后缀最大值最小的 \(i\)。那么要求的就是 \(j\) 前面第一个满足 \(a_i>a_j\) 的 \(i+1\)，可以单调栈解决。
现在有了修改，直接线段树维护单调栈（楼房重建线段树）即可。
复杂度 \(O((n+m)\log^2 n)\)。
// Problem: #2495. 「AHOI / HNOI2018」转盘
// Contest: LibreOJ
// URL: https://loj.ac/p/2495
// Memory Limit: 512 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define mt make_tuple
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef tuple<int, int, int> tu;
bool Med;
const int N = 1e5 + 100;
const int inf = 0x3f3f3f3f;
int n, m, op, a[N << 1];
int mx[N << 3], tr[N << 3];
#define ls x << 1
#define rs x << 1 | 1
#define mid ((l + r) >> 1)
int qry(int l, int r, int c, int x) {
if (l == r) return mx[x] <= c ? inf : c + l + 1;
if (mx[rs] < c) return qry(l, mid, c, ls);
return min(tr[x], qry(mid + 1, r, c, rs));
}
void pup(int l, int r, int x) {
mx[x] = max(mx[ls], mx[rs]);
tr[x] = qry(l, mid, mx[rs], ls);
}
void upd(int l, int r, int p, int c, int x) {
if (l == r) return mx[x] = c, void();
if (p <= mid) upd(l, mid, p, c, ls);
else upd(mid + 1, r, p, c, rs);
pup(l, r, x);
}
void solve() {
cin >> n >> m >> op;
for (int i = 1; i <= n; i++)
cin >> a[i], a[i + n] = a[i];
for (int i = 1; i <= (n << 1); i++)
upd(1, n << 1, i, a[i] - i, 1);
int lst = 0;
cout << (lst = min(1 + mx[1], tr[1]) + n - 1) << '\n';
while (m--) {
int x, y; cin >> x >> y;
x ^= op * lst, y ^= op * lst;
upd(1, n << 1, x, y - x, 1), upd(1, n << 1, x + n, y - n - x, 1);
cout << (lst = min(1 + mx[1], tr[1]) + n - 1) << '\n';
}
}
bool Mbe;
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cerr << (&Med - &Mbe) / 1048576.0 << " MB\n";
#ifdef FILE
freopen("1.in", "r", stdin);
freopen("1.out", "w", stdout);
#endif
int T = 1;
// cin >> T;
while (T--) solve();
cerr << (int)(1e3 * clock() / CLOCKS_PER_SEC) << " ms\n";
return 0;
}