#include<bits/stdc++.h>
using namespace std;
vector<pair<int,int>> UPDs[100100];
vector<set<int>> checkP[100100];
const int Z = 20;
vector<int> checkT[100100];
set<int> friens[100100];
int heights[100100];
vector<int> getH(int n,int pos){
set<int> st;
int x = lower_bound(checkT[n].begin(),checkT[n].end(),pos+1)-checkT[n].begin()-1,sz=size(UPDs[n]);
st=checkP[n][x];
int y = lower_bound(UPDs[n].begin(),UPDs[n].end(),make_pair(checkT[n][x]+1,0))-UPDs[n].begin();
while(y<sz&&UPDs[n][y].first <=pos){
int k = UPDs[n][y].second;
if(st.count(k))
st.erase(k);
else st.insert(k);
y++;
}
vector<int>v;
for(auto k:st)
v.push_back(heights[k]);
sort(v.begin(),v.end());
return v;
}
int GA(vector<int>a,vector<int>b){
if(a.empty()||b.empty())
return 1e9;
int l=0,r=0,n=size(a),m=size(b);
int ans=1e9;
while(l<n&&r<m){
if(a[l]==b[r])return 0;
if(a[l]<b[r])
ans=min(ans,b[r]-a[l++]);
else ans=min(ans,a[l]-b[r++]);
}
return ans;
}
void adup(int u, int v,int t){
UPDs[u].push_back({t,v});
if(friens[u].count(v))
friens[u].erase(v);
else friens[u].insert(v);
if(UPDs[u].size() % Z ==0)
checkP[u].push_back(friens[u]),checkT[u].push_back(t);
}
int question(int a,int b,int v){
return GA(getH(a,v),getH(b,v));
}
void init(int n,int D,int H[]){
vector<int>v;
for(int i=0;i<n;i++)
heights[i]=H[i],checkP[i].resize(1),checkT[i].resize(1);
}
void curseChanges(int u,int A[],int B[]) {
for(int i=0;i<u;i++){
int a,b;
a=A[i];
b=B[i];
adup(a,b,i+1);
adup(b,a,i+1);
}
}
