#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vii;
typedef pair<int,int> pi;
typedef vector<pi> pii;
typedef tuple<int,int,int> ti;
typedef vector<ll> li;
typedef vector<li> lii;
#define REP(i,a,b) for(int i=a;i<b;i++)
#define F first
#define S second
#define PB push_back
#define LSOne(s) ((s)&(-s))
#define all(x) (x).begin(),(x).end()
ll INF=1000000000000000010;
int inf=1e9;
ll M=1e9+7;
vi h;
int n;
vector<vector<vector<pi>>> a;
vii b;
set<pi> st;
void init(int N, int D, int H[]) {
n=N;
h.resize(n);
REP(i,0,n)h[i]=H[i];
a.resize(n);
b.resize(n);
}
void curseChanges(int U, int A[], int B[]) {
REP(i,0,U){
int x=A[i],y=B[i];
if(x>y)swap(x,y);
if(st.count({x,y})){
REP(j,0,b[x].size())if(b[x][j]==y){
b[x][j]=-1;
a[x][j].PB({i,-1});
break;
}
REP(j,0,b[y].size())if(b[y][j]==x){
b[y][j]=-1;
a[y][j].PB({i,-1});
break;
}
st.erase({x,y});
}
else{
bool f=1;
REP(j,0,b[x].size())if(b[x][j]==-1){
b[x][j]=y;
a[x][j].PB({i,y});
f=0;
break;
}
if(f){
b[x].PB(y);
a[x].PB({{i,y}});
}
f=1;
REP(j,0,b[y].size())if(b[y][j]==-1){
b[y][j]=x;
a[y][j].PB({i,x});
f=0;
break;
}
if(f){
b[y].PB(x);
a[y].PB({{i,x}});
}
st.insert({x,y});
}
}
}
int question(int x, int y, int v) {
vi X,Y;
REP(i,0,a[x].size())if(!a[x][i].empty()){
auto it=lower_bound(all(a[x][i]),make_pair(v,-2));
if(it==a[x][i].begin())continue;
it--;
if(it->S!=-1)X.PB(it->S);
}
REP(i,0,a[y].size())if(!a[y][i].empty()){
auto it=lower_bound(all(a[y][i]),make_pair(v,-2));
if(it==a[y][i].begin())continue;
it--;
if(it->S!=-1)Y.PB(it->S);
}
REP(i,0,X.size())X[i]=h[X[i]];
REP(i,0,Y.size())Y[i]=h[Y[i]];
sort(all(X));sort(all(Y));
X.erase(unique(all(X)),X.end());
Y.erase(unique(all(Y)),Y.end());
int ans=inf;
REP(i,0,X.size()){
auto it=lower_bound(all(Y),X[i]);
if(it!=Y.end())ans=min(ans,abs(*it-X[i]));
if(it!=Y.begin()){
it--;
ans=min(ans,abs(*it-X[i]));
}
}
return ans;
}
