#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
const int B = 1000;
set<int> curr[N];
vector<set<int> > g[N];
int n, D, h[N], a[N], b[N], m;
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>{});
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]);
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(i % B == 0) {
for(int j=0; j<n; j++)
g[j].push_back(curr[j]);
}
}
}
int question(int x, int y, int v) {
int ans = 1e9;
int id = v / B;
set<int> stL = g[x][id];
set<int> stR = g[y][id];
for(int i=id*B+1; i<=v; i++) {
if(a[i] == x) {
if(stL.count(b[i]))
stL.erase(b[i]);
else
stL.insert(b[i]);
}
if(a[i] == y) {
if(stR.count(b[i]))
stR.erase(b[i]);
else
stR.insert(b[i]);
}
if(b[i] == x) {
if(stL.count(a[i]))
stL.erase(a[i]);
else
stL.insert(a[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;
}
