#include<bits/stdc++.h>
typedef long long ll;
#define pb push_back
#define fr first
#define sc second
#define endl '\n'
using namespace std;
#define mid ((left+right)>>1)
int n;
int h[100023];
map<int,vector<int>>v[100023];
map<int,int>mp[100023];
vector<int>sta[100023];
void init(int N, int D, int H[]){
n=N;
for(int i=0;i<n;i++){
h[i]=H[i];
v[i][0]=vector<int>();
}
}
void f(int tar,int val,int tim){
mp[tar][tim]=val;
sta[tar].pb(val);
if(sta[tar].size()==10){
set<int>cnt;
for(int x:sta[tar]){
if(cnt.count(x))cnt.erase(x);
else cnt.insert(x);
}
sta[tar].clear();
vector<int>&las=(--v[tar].end())->sc;
vector<int>&cur=v[tar][tim];
for(int x:las){
if(cnt.count(x)){
cnt.erase(x);
continue;
}
cur.pb(x);
}
for(int x:cnt){
cur.pb(x);
}
cnt.clear();
}
}
void curseChanges(int U, int A[], int B[]){
for(int i=1;i<=U;i++){
int a=A[i-1],b=B[i-1];
f(a,b,i);
f(b,a,i);
}
}
_Rb_tree_iterator<pair<const int,vector<int>>>itr1;
_Rb_tree_const_iterator<pair<const int,int>>itr;
vector<int> cal(int tar,int tim){
itr1=--v[tar].upper_bound(tim);
vector<int>&las=itr1->sc;
int curtim=itr1->fr;
itr=mp[tar].upper_bound(curtim);
set<int>cnt;
while(itr!=mp[tar].end()&&itr->fr<=tim){
if(cnt.count(itr->sc)){
cnt.erase(itr->sc);
}
else cnt.insert(itr->sc);
itr++;
}
vector<int>res;
for(int x:las){
if(cnt.count(x)){
cnt.erase(x);
continue;
}
res.pb(x);
}
for(int x:cnt){
res.pb(x);
}
sort(res.begin(),res.end(),[&](const int &x,const int &y){
return h[x]<h[y];
});
return res;
}
int question(int x, int y, int v){
int res=1e9;
vector<int>a=cal(x,v),b=cal(y,v);
int ust=0;
for(int x:a){
while(ust<b.size()&&h[b[ust]]<h[x])ust++;
if(ust<b.size()){
res=min(res,abs(h[x]-h[b[ust]]));
}
if(ust-1>=0){
res=min(res,abs(h[x]-h[b[ust-1]]));
}
}
return res;
}
