#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
const int B = 300;
set<int> curr[N];
vector<set<int> > g[N];
vector<int> T[N], ord[N];
int n, D, h[N], a[N], b[N], m, cnt[N];
bool cmp(int i, int j) {
return h[i] < h[j];
}
void init(int _N, int _D, int H[]) {
n = _N;
D = _D;
for(int i=0; i<n; i++) h[i] = H[i];
}
void curseChanges(int U, int _A[], int _B[]) {
m = U;
for(int i=0; i<n; i++) {
g[i].push_back(set<int>{});
T[i].push_back(0);
ord[i].push_back(0);
}
for(int i=1; i<=m; i++) {
a[i] = _A[i-1];
b[i] = _B[i-1];
if(a[i] > b[i]) swap(a[i], b[i]);
cnt[a[i]]++;
cnt[b[i]]++;
ord[a[i]].push_back(i);
ord[b[i]].push_back(i);
if(curr[a[i]].count(b[i])) {
curr[a[i]].erase(b[i]);
curr[b[i]].erase(a[i]);
} else {
curr[a[i]].insert(b[i]);
curr[b[i]].insert(a[i]);
}
if(cnt[a[i]] == B) {
g[a[i]].push_back(curr[a[i]]);
T[a[i]].push_back(i);
cnt[a[i]] = 0;
}
if(cnt[b[i]] == B) {
g[b[i]].push_back(curr[b[i]]);
T[b[i]].push_back(i);
cnt[b[i]] = 0;
}
}
for(int i=0; i<n; i++) {
if(T[i].back() != m) {
T[i].push_back(m);
g[i].push_back(curr[i]);
}
}
}
int question(int x, int y, int v) {
int ans = 1e9;
int px = upper_bound(T[x].begin(), T[x].end(), v) - T[x].begin() - 1;
int py = upper_bound(T[y].begin(), T[y].end(), v) - T[y].begin() - 1;
set<int> stL = g[x][px];
set<int> stR = g[y][py];
int tx = upper_bound(ord[x].begin(), ord[x].end(), T[x][px]) - ord[x].begin();
int ty = upper_bound(ord[y].begin(), ord[y].end(), T[y][py]) - ord[y].begin();
for(int j=tx; j<ord[x].size(); j++) {
if(ord[x][j] > v) break;
int i = ord[x][j];
// cout << x << " " << i << endl;
if(a[i] == x) {
if(stL.count(b[i]))
stL.erase(b[i]);
else
stL.insert(b[i]);
}
if(b[i] == x) {
if(stL.count(a[i]))
stL.erase(a[i]);
else
stL.insert(a[i]);
}
}
for(int j=ty; j<ord[y].size(); j++) {
if(ord[y][j] > v) break;
int i = ord[y][j];
// cout << y << " " << i << endl;
if(a[i] == y) {
if(stR.count(b[i]))
stR.erase(b[i]);
else
stR.insert(b[i]);
}
if(b[i] == y) {
if(stR.count(a[i]))
stR.erase(a[i]);
else
stR.insert(a[i]);
}
}
vector<int> L(stL.begin(), stL.end());
vector<int> R(stR.begin(), stR.end());
if(L.empty() || R.empty()) return 1e9;
sort(L.begin(), L.end(), cmp);
sort(R.begin(), R.end(), cmp);
int j = 0;
for(int i=0; i<R.size(); i++) {
while(j+1 < L.size() && h[L[j+1]] <= h[R[i]]) j++;
ans = min(ans, abs(h[L[j]] - h[R[i]]));
}
j = L.size() - 1;
for(int i=R.size()-1; i>=0; i--) {
while(j && h[L[j-1]] >= h[R[i]]) j--;
ans = min(ans, abs(h[L[j]] - h[R[i]]));
}
return ans;
}
