#include <bits/stdc++.h>
#define ll int
#define sz(x) int(x.size())
#define forn(i, n) for (i = 0; i < n; i++)
#define all(x) x.begin(), x.end()
#define pb push_back
#define mp make_pair
#define fr first
#define se second
using namespace std;
const int MAXN = 1e5 + 1;
const int SQ=318;
const int has=1000;
const int tam=(MAXN+MAXN-1)/SQ;
ll h[MAXN], n;
void init(int N, int D, int H[])
{
ll i;
for (i = 0; i < N; i++)
h[i] = H[i];
n=N;
}
vector<pair<ll,ll>>ars[MAXN];
unordered_map<ll,ll> ma;
unordered_map<ll,set<ll>>grafo;
void curseChanges(int U, int A[], int B[])
{
ll i, j, k;
for(i=0; i<U; i++)
{
ars[A[i]].pb({B[i],i});
ars[B[i]].pb({A[i],i});
}
for(i=0; i<n; i++)
{
for(j=0; j<sz(ars[i]); j++)
{
k=j/SQ;
if(ma[i*has+k]==0&&k>0)
grafo[i*has+k]=grafo[i*has+k-1];
ma[i*has+k]=ars[i][j].se+1;
auto it=grafo[i*has+k].find(ars[i][j].fr);
if(it==grafo[i*has+k].end())
grafo[i*has+k].insert(ars[i][j].fr);
else
grafo[i*has+k].erase(it);
}
}
}
ll k, ul, j, mi, ant, i;
vector<ll>retX,retY;
set<ll>adyX;
int question(int x, int y, int v)
{
v--;
retX.clear();
retY.clear();
auto calc=[&]()
{
adyX.clear();
k=0, ul=-1;
for(k; k<=(sz(ars[x])-1)/SQ; k++)
{
if(ma[x*has+k]-1>v)
break;
ul=k;
}
if(ul>=0)
adyX=grafo[x*has+ul];
for(j=SQ*(ul+1); j<min(sz(ars[x]),SQ*(ul+2)); j++)
{
if(ars[x][j].se<=v)
{
auto it=adyX.find(ars[x][j].fr);
if(it==adyX.end())
adyX.insert(ars[x][j].fr);
else
adyX.erase(it);
}
else
break;
}
for(auto &k:adyX)
retX.pb(h[k]);
sort(all(retX));
};
mi = 1e9, ant=-1;
calc();
if(sz(retX) == 0)
return mi;
swap(x,y);
swap(retX,retY);
calc();
if(sz(retX) == 0)
return mi;
j=0;
for(i=0; i<sz(retX); i++)
{
while(j+1<sz(retY)&&retY[j+1]<retX[i])
j++;
mi=min(mi,abs(retY[j]-retX[i]));
if(j+1<sz(retY))
mi=min(mi,abs(retY[j+1]-retX[i]));
}
return mi;
}
