#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
using namespace std;
const int maxn=1e5, maxd=500;
int broj[2];
int ok[2][maxd];
struct tournament{
vector < vector < int > > t;
int n;
tournament(int sz){
n=sz;
for(int i=0; i<n*2; i++){
t.push_back({});
}
}
void update(int l, int r, int val){
for(l+=n, r+=n; l<r; l>>=1, r>>=1){
if(l&1){
t[l++].push_back(val);
}
if(r&1){
t[--r].push_back(val);
}
}
}
void query(int x, int koji){
x+=n;
while(x>0){
for(int i=0; i<(int)t[x].size(); i++){
ok[koji][broj[koji]++]=t[x][i];
}
x>>=1;
}
}
};
int n, d;
int h[maxn];
void init(int N, int D, int H[]){
n=N;
d=D;
for(int i=0; i<n; i++){
h[i]=H[i];
}
}
int br[maxn];
vector < int > kad[maxn];
set < pair < int, int > > poc[maxn];
vector < pair < pair < int, int >, int > > upit[maxn];
vector < tournament > V;
void curseChanges(int u, int a[], int b[]){
set < pair < int, int > >::iterator it;
for(int i=0; i<u; i++){
it=poc[a[i]].lower_bound({b[i], 0});
if(it==poc[a[i]].end() || it->first!=b[i]){
poc[a[i]].insert({b[i], br[a[i]]});
poc[b[i]].insert({a[i], br[b[i]]});
}
else{
upit[a[i]].push_back({{it->second, br[a[i]]}, b[i]});
poc[a[i]].erase(it);
it=poc[b[i]].lower_bound({a[i], 0});
upit[b[i]].push_back({{it->second, br[b[i]]}, a[i]});
poc[b[i]].erase(it);
}
br[a[i]]++;
br[b[i]]++;
kad[a[i]].push_back(i+1);
kad[b[i]].push_back(i+1);
}
for(int i=0; i<n; i++){
tournament T(br[i]);
while(!upit[i].empty()){
T.update(upit[i].back().first.first, upit[i].back().first.second, upit[i].back().second);
upit[i].pop_back();
}
while(!poc[i].empty()){
T.update(poc[i].begin()->second, br[i], poc[i].begin()->first);
poc[i].erase(poc[i].begin());
}
V.push_back(T);
}
}
int binary(int x, int val){
int lo=-1, hi=kad[x].size()-1, mid;
while(lo<hi){
mid=(lo+hi+1)/2;
if(kad[x][mid]>val){
hi=mid-1;
}
else{
lo=mid;
}
}
return lo;
}
bool cmp(int a, int b){
return h[a]<h[b];
}
int question(int x, int y, int v){
int br1=binary(x, v);
int br2=binary(y, v);
if(br1==-1 || br2==-1){
return 1e9;
}
broj[0]=0;
V[x].query(br1, 0);
broj[1]=0;
V[y].query(br2, 1);
sort(ok[0], ok[0]+broj[0], cmp);
sort(ok[1], ok[1]+broj[1], cmp);
int pos1=0, pos2=0;
int sol=1e9;
while(pos1<broj[0] && pos2<broj[1]){
sol=min(sol, abs(h[ok[0][pos1]]-h[ok[1][pos2]]));
if(h[ok[0][pos1]]<h[ok[1][pos2]]){
pos1++;
}
else{
pos2++;
}
}
return sol;
}
