// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
#define len(x) (int)x.size()
#define tm (tl + tr >> 1)
#define ls tl, tm
#define rs tm + 1, tr
#define ll logn long
using namespace std;
namespace {
const int N = 2e5 + 3;
int n, d, m, h[N], cnt[N];
set <int> s[N];
vector <int> mex;
struct node{
bool val;
int l, r;
node () : val(0), l(0), r(0) {}
} t[N * 50];
}
int sz = 0, root[N];
void upd(int pos, bool val, int v, int &u, ll tl = 1, ll tr = 1ll * n * n) {
u = ++sz;
if (tl == tr) {
t[u].val = val;
return;
}
if (pos <= tm) {
t[u].r = t[v].r;
upd(pos, val, t[v].l, t[u].l, ls);
} else {
t[u].l = t[v].l;
upd(pos, val, t[v].r, t[u].r, rs);
}
int lv = t[u].l, rv = t[u].r;
t[u].val = t[lv].val | t[rv].val;
}
bool fnd(int pos, int v, ll tl = 1, ll tr = 1ll * n * n) {
if (!v || !t[v].val) return false;
if (tl == tr) return t[v].val;
if (pos <= tm) return fnd(pos, t[v].l, ls);
else return fnd(pos, t[v].r, rs);
}
void get(int l, int r, int v, ll tl = 1, ll tr = 1ll * n * n) {
if (!v || !t[v].val || r < tl || tr < l) return;
if (tl == tr) {
mex.push_back(tl);
return;
}
get(l, r, t[v].l, ls);
get(l, r, t[v].r, rs);
}
void init(int N, int D, int H[]) {
n = N;
d = D;
for (int i = 1; i <= n; i++) {
h[i] = H[i - 1];
}
}
void curseChanges(int U, int A[], int B[]) {
m = U;
root[0] = ++sz;
for (int i = 1; i <= m; i++) {
int a = A[i - 1] + 1, b = B[i - 1] + 1;
int rot = root[i - 1];
if (!fnd((a - 1) * n + b, root[i - 1])) {
upd((a - 1) * n + b, 1, root[i - 1], root[i]);
rot = root[i];
} else {
upd((a - 1) * n + b, 0, root[i - 1], root[i]);
rot = root[i];
}
swap(a, b);
if (!fnd((a - 1) * n + b, root[i - 1])) {
upd((a - 1) * n + b, 1, rot, root[i]);
} else {
upd((a - 1) * n + b, 0, rot, root[i]);
}
}
}
int question(int x, int y, int v) {
x++;
y++;
mex.clear();
get((y - 1) * n + 1, y * n, root[v]);
vector <int> act;
for (int it: mex) {
act.push_back(h[it - (y - 1) * n]);
// cout << y << ' ' << it - (y - 1) * n << '\n';
}
sort(act.begin(), act.end());
int ans = 1e9;
if (!len(act)) return ans;
mex.clear();
get((x - 1) * n + 1, x * n, root[v]);
for (int it: mex) {
int i = it - (x - 1) * n;
// cout << x << ' ' << i << '\n';
int l = 0, r = len(act) - 1;
while (l + 1 < r) {
int md = l + r >> 1;
if (h[i] <= act[md]) r = md;
else l = md;
}
ans = min({ans, abs(h[i] - act[l]), abs(h[i] - act[r])});
}
return ans;
}
