#include <bits/stdc++.h>
using namespace std;
#define sz size()
#define S second
#define F first
const int N=(int)2e5+3;
int h[N],a[N],b[N];
int cnt[N],cnt1[N];
int n;
int m;
void init(int N, int D, int H[]) {
for(int i=0;i<N;i++)h[i]=H[i];
}
vector<pair<int,int>>t[N*4];
void upd(int l,int r,pair<int,int>x,int v=1,int tl=1,int tr=n){
if(tl>=l&&tr<=r){
t[v].push_back(x);
t[v].push_back({x.S,x.F});
return;
}
if(tl>r||l>tr)return;
int md=(tl+tr)>>1;
upd(l,r,x,v+v,tl,md);
upd(l,r,x,v+v+1,md+1,tr);
}
void sort_tree(int v=1,int tl=1,int tr=n){
sort(t[v].begin(),t[v].end());
if(tl==tr)return;
int md=(tl+tr)>>1;
sort_tree(v+v,tl,md);
sort_tree(v+v+1,md+1,tr);
}
set<pair<pair<int,int>,int>>st;
void curseChanges(int U, int A[], int B[]) {
n=U;
for(int i=0;i<n;i++){
if(A[i]>B[i])swap(A[i],B[i]);
auto it=st.lower_bound({{A[i],B[i]},-1});
if(it==st.end()||it->F.F!=A[i]||it->F.S!=B[i]){
st.insert({{A[i],B[i]},i});
}
else{
int l=it->S+1,r=i+1;
st.erase(it);
upd(l,r-1,{A[i],B[i]});
}
}
for(auto [to,pos]:st)upd(pos+1,n,to);
sort_tree();
}
int needA,needB;
vector<int>nowA,nowB;
void get(int pos,int v=1,int tl=1,int tr=n){
int j=lower_bound(t[v].begin(),t[v].end(),make_pair(needA,-1))-t[v].begin();
for(;j<(int)t[v].sz;j++){
if(t[v][j].F!=needA)break;
nowA.push_back(h[t[v][j].S]);
}
j=lower_bound(t[v].begin(),t[v].end(),make_pair(needB,-1))-t[v].begin();
for(;j<(int)t[v].sz;j++){
if(t[v][j].F!=needB)break;
nowB.push_back(h[t[v][j].S]);
}
if(tl==tr)return;
int md=(tl+tr)>>1;
if(pos<=md)get(pos,v+v,tl,md);
else get(pos,v+v+1,md+1,tr);
}
int question(int x, int y, int v) {
needA=x;
needB=y;
nowA.clear();
nowB.clear();
get(v+1);
if(nowA.empty()||nowB.empty())return (int)1e9;
sort(nowA.begin(),nowA.end());
sort(nowB.begin(),nowB.end());
int mn=(int)1e9;
int j=0;
for(auto to:nowA){
while(j<(int)nowA.sz-1&&nowB[j]<to)j++;
mn=min(mn,abs(nowB[j]-to));
if(j>0)mn=min(mn,abs(nowB[j-1]-to));
}
return mn;
}
