#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize(2)
map<int,set<int>>checkpoints[100100];
vector<pair<int,int>> upds[100100];
set<int>stuf[100100];
int h[100100],rev[100100],cod[100100],nnn;
void init(int n,int D,int H[]){
nnn=N; vector<int>v;
for(int i=0;i<n;i++) h[i]=H[i];
v.push_back(i),checkpoints[i][-1];
sort(v.begin(),v.end(),[](int a,int b){return h[a]<h[b];});
for(int i=0;i<n;i++)
rev[cod[v[i]]=i]=v[i];
}
int question(int a,int b,int v){
a=cod[a],b=cod[b];
vector<int>A,B;
auto it=--checkpoints[a].lower_bound(v);
set<int>X;
swap(X,it->second);
auto it2=lower_bound(upds[a].begin(),upds[a].end(),make_pair(it->first+1,0));
int I=it2-upds[a].begin(),begI=I;
for(;I<upds[a].size()&&upds[a][I].first<v;I++)
if(X.count(upds[a][I].second))
X.erase(upds[a][I].second);
else X.insert(upds[a][I].second);
for(auto i:X)A.push_back(h[rev[i]]);
while(--I>=begI)
if(X.count(upds[a][I].second))
X.erase(upds[a][I].second);
else X.insert(upds[a][I].second);
swap(X,it->second);
it=--checkpoints[b].lower_bound(v);
swap(X,it->second);
it2=lower_bound(upds[b].begin(),upds[b].end(),make_pair(it->first+1,0));
I=it2-upds[b].begin(),begI=I;
for(;I<upds[b].size()&&upds[b][I].first<v;I++)
if(X.count(upds[b][I].second))
X.erase(upds[b][I].second);
else X.insert(upds[b][I].second);
for(auto i:X)B.push_back(h[rev[i]]);
while(--I>=begI)
if(X.count(upds[b][I].second))
X.erase(upds[b][I].second);
else X.insert(upds[b][I].second);
swap(X,it->second);
int l=0,r=0,res=1e9;
while(l<A.size()&&r<B.size()){
res=min(res,abs(A[l]-B[r]));
if(A[l]<B[r])l++;
else r++;
}
return res;
}
void curseChanges(int u,int A[],int B[]) {
for(int i=0;i<u;i++){
int a,b;
a=A[i];
b=B[i];
a=cod[a];
b=cod[b];
if(stuf[a].count(b))
stuf[a].erase(b),
stuf[b].erase(a);
else stuf[a].insert(b),
stuf[b].insert(a);
upds[a].push_back({i,b});
upds[b].push_back({i,a});
if(upds[a].size()%30==0)
checkpoints[a][i]=stuf[a];
if(upds[b].size()%30==0)
checkpoints[b][i]=stuf[b];
}
for (int i=0;i<n;i++)stuf[i].clear();
}
