#include <bits/stdc++.h>
#pragma GCC opimize("O3")
using namespace std;
typedef pair<int,int> pii;
const int C=40;
int n,d,u,q,h[100005],p1[200005],p2[200005];
unordered_set<int> setik[100005];
vector<int> vals[100005];
vector< pair< int, vector<int> > > checkpoint[100005];
vector<int> ck[100005];
vector<int> v;
vector<int> v1;
vector<int> rez;
vector<int> V1,V2,t;
bool isthere[100005];
pii day[200005];
int findpoz(int poz,int who)
{
if(day[poz].first==who)
return p1[poz];
else
return p2[poz];
}
void buildv(int x,int zi,int index)
{
rez.clear();
v1.clear();
int st=0;
int dr=checkpoint[x].size();
int pozmax=-1;
dr--;
while(st<=dr)
{
int mij=(st+dr)/2;
if(checkpoint[x][mij].first<=zi)
{
pozmax=max(pozmax,mij);
st=mij+1;
}
else
dr=mij-1;
}
t.clear();
if(pozmax!=-1)
{
for(int i=0;i<checkpoint[x][pozmax].second.size();i++)
{
int p=checkpoint[x][pozmax].second[i];
v1.push_back(p);
isthere[p]=1;
}
int poz=findpoz(checkpoint[x][pozmax].first,x);
int nrit=0;
for(int i=poz+1;i<vals[x].size()&&vals[x][i]<=zi;i++)
{
nrit++;
int z=vals[x][i];
int nod=(x^day[z].first^day[z].second);
t.push_back(nod);
if(isthere[nod]==0)
isthere[nod]=1;
else
isthere[nod]=0;
}
}
if(!t.empty())
{
for(int j=0;j<t.size();j++)
v1.push_back(t[j]);
}
if(v1.empty())
{
if(index==1)
V1=rez;
else
V2=rez;
return;
}
for(int i=0;i<v1.size();i++)
if(isthere[v1[i]]==1)
{
rez.push_back(h[v1[i]]);
isthere[v1[i]]=0;
}
sort(rez.begin(),rez.end());
if(index==1)
V1=rez;
else
V2=rez;
}
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[])
{
u=U;
for(int i=1;i<=u;i++)
{
int a,b;
a=A[i-1];
b=B[i-1];
day[i]={a,b};
vals[a].push_back(i);
p1[i]=vals[a].size();
p1[i]--;
vals[b].push_back(i);
p2[i]=vals[b].size();
p2[i]--;
if(setik[a].find(b)!=setik[a].end())
{
setik[a].erase(b);
setik[b].erase(a);
}
else
{
setik[a].insert(b);
setik[b].insert(a);
}
if((int)vals[a].size()%C==1)
{
vector<int> aux;
for(int j:setik[a])
aux.push_back(j);
checkpoint[a].push_back({i,aux});
}
if((int)vals[b].size()%C==1)
{
vector<int> aux;
for(int j:setik[b])
aux.push_back(j);
checkpoint[b].push_back({i,aux});
}
}
}
int question(int x,int y,int zi)
{
V1.clear();
V2.clear();
buildv(x,zi,1);
buildv(y,zi,2);
if(V1.empty()||V2.empty())
{
return 1000000000;
}
int ans=1e9;
int j=0;
for(int i=0;i<V1.size();i++)
{
j=max(j,0);
while(j<V2.size()&&V2[j]<=V1[i])
j++;
j--;
if(j>=0)
ans=min(ans,abs(V1[i]-V2[j]));
if(j+1<V2.size())
ans=min(ans,abs(V1[i]-V2[j+1]));
}
return ans;
}
