#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N=1e5+5;
int H[MAX_N];
int N;
int D;
int d=50;
vector<vector<pair<int, set<int>>>> changes(MAX_N, vector<pair<int, set<int>>> (1));
void init(int NN, int DD, int HH[]){
N=NN;
D=DD;
for(int i=0; i<N; i++) H[i]=HH[i];
for(int i=0; i<N; i++){
changes[i][0].first=0;
changes[i][0].second.clear();
}
}
vector<vector<pair<int, int>>> upd(MAX_N);
void curseChanges(int UU, int AA[], int BB[]){
for(int i=0; i<UU; i++){
upd[AA[i]].push_back({i+1, BB[i]});
upd[BB[i]].push_back({i+1, AA[i]});
}
for(int i=0; i<N; i++){
for(int r=d; (int)upd[i].size()>=r; r+=d){
changes[i].push_back(changes[i][changes[i].size()-1]);
changes[i][r/d].first=upd[i][r-1].first;
for(int j=r-d; j<r; j++){
//add all updates
int u=upd[i][j].second;
if((changes[i][r/d].second).count(u)){
changes[i][r/d].second.erase(u);
}
else changes[i][r/d].second.insert(u);
}
}
}
}
set<int> query(int p, int day){
int s=upd[p].size();
int r=0;
//binary search here
int a=0, b=changes[p].size()-1;
if(changes[p][b].first<=day){
r=b;
}
else{
while(a+1<b){
int c=(a+b)/2;
if(changes[p][c].first<=day){
a=c;
}
else b=c;
}
r=a;
}
set<int> ans=changes[p][r].second;
for(int t=r*d; t<upd[p].size() && upd[p][t].first<=day; t++){
int u=upd[p][t].second;
if(ans.count(u)){
ans.erase(u);
}
else ans.insert(u);
}
return ans;
}
int question(int x, int y, int v){
//find the sets
set<int> ans1=query(x, v), ans2=query(y, v);
if(ans1.size()==0 || ans2.size()==0) return 1e9;
vector<ll> h1;
vector<ll> h2;
for(int r : ans1){
h1.push_back(H[r]);
}
for(int r : ans2){
h2.push_back(H[r]);
}
h2.push_back(-1e9);
h2.push_back(2e9);
sort(h1.begin(), h1.end());
sort(h2.begin(), h2.end());
ll m=1e9;
for(int i=0, e=0; i<h1.size();){
if(h2[e+1]<h1[i]){
e++;
continue;
}
m=min(m, h1[i]-h2[e]);
m=min(m, h2[e+1]-h1[i]);
i++;
}
return m;
}
