#include<bits/stdc++.h>
using namespace std;
#define inf (int)1e9
#define nl '\n'
const int N = 1e5+1, c = 20;
vector<pair<int, vector<int>>> g[N];
int h[N], cnt[N];
int n;
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}});
else g[x].push_back({i, vector<int>(cgx.begin(), cgx.end())});
};
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];
};
for(int y : gx[l].second) cnt[y]++;
for(int i = l+1; i <= r; i++){
int y = gx[i].second[0];
cnt[y]++;
}
v.clear();
for(int y : gx[l].second){
if(cnt[y] % 2) v.push_back(h[y]);
}
for(int i = l+1; i <= r; i++){
int y = gx[i].second[0];
if(cnt[y] % 2) v.push_back(h[y]);
}
for(int y : gx[l].second) cnt[y] = 0;
for(int i = l+1; i <= r; i++){
int y = gx[i].second[0];
cnt[y] = 0;
}
sort(v.begin(), v.end());
return v;
}
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;
}
