#include<bits/stdc++.h>
using namespace std;
#define inf (int)1e9
#define nl '\n'
const int N = 1e5+1, c = 35;
vector<pair<int, vector<int>>> g[N];
int h[N];
int n;
bool cmp(int x, int y){
return h[x] < h[y];
}
void init(int N, int D, int H[]){
n = N;
for(int i = 0; i < n; i++) h[i] = H[i];
}
void curseChanges(int u, int a[], int b[]){
set<int> cg[n];
for(int i = 1; i <= u; i++){
auto add = [&](int x, int y){
auto &cgx = cg[x];
if(cgx.count(y)) cgx.erase(y);
else cgx.insert(y);
if(g[x].size() % c != 0){
g[x].push_back({i, {y}});
return;
}
vector<int> v(cgx.begin(), cgx.end());
sort(v.begin(), v.end(), cmp);
g[x].push_back({i, v});
};
add(a[i-1], b[i-1]);
add(b[i-1], a[i-1]);
}
}
vector<int> get(int x, int d){
auto &gx = g[x];
int n = gx.size();
vector<int> v = {inf};
int r = upper_bound(gx.begin(), gx.end(), pair(d, v)) - gx.begin() - 1;
if(r < 0) return {};
int l = r - (r % c);
auto cmp = [&](int x, int y){
return h[x] < h[y];
};
auto &cg = gx[l].second;
set<int> st;
for(int i = l+1; i <= r; i++){
int y = gx[i].second[0];
if(st.count(y)) st.erase(y);
else st.insert(y);
}
vector<int> ng(st.begin(), st.end());
sort(ng.begin(), ng.end(), cmp);
v.resize(cg.size() + ng.size());
merge(cg.begin(), cg.end(), ng.begin(), ng.end(), v.begin());
vector<int> res;
for(int i = 0; i+1 < (int)v.size(); i++){
if(v[i] == v[i+1]) i++;
else res.push_back(h[v[i]]);
}
return res;
}
int question(int p, int q, int v){
auto v1 = get(p, v);
auto v2 = get(q, v);
int s1 = v1.size(), s2 = v2.size();
int ans = inf;
for(int i = 0, j = -1; i < s1; i++){
while(j+1 < s2 and v2[j+1] <= v1[i]) j++;
ans = min(ans, min(j >= 0 ? v1[i] - v2[j] : inf, j+1 < s2 ? v2[j+1] - v1[i] : inf));
}
return ans;
}
