#include <bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define file(s) if (fopen(s".in", "r")) freopen(s".in", "r", stdin), freopen(s".out", "w", stdout)
#define all(a) a.begin() , a.end()
#define F first
#define S second
using namespace std;
using ll = long long;
const ll N = 2e5+5 , inf = 2e9 + 7;
const ll INF = 1e18 , mod = 1e9+7;
int n , d , t , h[N] , a[N] , b[N];
vector<pair<int,int>> vec[N*4];
void init(int N, int D, int H[]) {
n = N; d = D;
for(int i = 0; i < N; i++) h[i] = H[i];
}
void build(int v, int tl , int tr){
sort(all(vec[v]));
if(tl == tr) return;
int tm = (tl+tr) >> 1;
build(v*2,tl,tm);
build(v*2+1,tm+1,tr);
}
void upd(int v, int tl , int tr , int l , int r , int x , int y){
if(l <= tl && tr <= r){
vec[v].push_back({x,h[y]});
vec[v].push_back({y,h[x]});
return;
}
if(tl > r || tr < l) return;
int tm = (tl+tr) >> 1;
upd(v*2,tl,tm,l,r,x,y);
upd(v*2+1,tm+1,tr,l,r,x,y);
}
int ans = 1e9;
vector<int> vx , vy;
void get(int v, int tl , int tr , int pos , int x , int y){
int l = 0 , r = vec[v].size()-1 , res = vec[v].size();
while(l <= r){
int md = (l+r) >> 1;
if(vec[v][md].F >= x){
res = md;
r = md-1;
} else {
l = md+1;
}
}
while(res < vec[v].size() && vec[v][res].F == x){
vx.push_back(vec[v][res].S);
res++;
}
l = 0 , r = vec[v].size()-1 , res = vec[v].size();
while(l <= r){
int md = (l+r) >> 1;
if(vec[v][md].F >= y){
res = md;
r = md-1;
} else {
l = md+1;
}
}
while(res < vec[v].size() && vec[v][res].F == y){
vy.push_back(vec[v][res].S);
res++;
}
if(tl == tr) return;
int tm = (tl+tr) >> 1;
if(pos <= tm){
get(v*2,tl,tm,pos,x,y);
} else {
get(v*2+1,tm+1,tr,pos,x,y);
}
}
void curseChanges(int U, int A[], int B[]) {
t = U;
for(int i = 0; i < t; i++){
a[i] = A[i];
b[i] = B[i];
}
map<pair<int,int>,int> mp;
for(int i = 0; i < t; i++){
if(mp[{a[i],b[i]}] == 0){
mp[{a[i],b[i]}] = i+1;
mp[{b[i],a[i]}] = i+1;
} else {
int mx = mp[{a[i],b[i]}];
upd(1,0,t,mx-1,i-1,a[i],b[i]);
mp[{a[i],b[i]}] = 0;
mp[{b[i],a[i]}] = 0;
}
}
for(int i = 0; i < t; i++){
if(mp[{a[i],b[i]}] > 0){
int mx = mp[{a[i],b[i]}];
upd(1,0,t,mx-1,t-1,a[i],b[i]);
mp[{a[i],b[i]}] = 0;
mp[{b[i],a[i]}] = 0;
}
}
build(1,0,t);
}
int question(int x, int y, int v) {
vx.clear();
vy.clear();
get(1,0,t,v-1,x,y);
sort(all(vx));
sort(all(vy));
ans = 1e9;
for(int z : vx){
int it = lower_bound(all(vy) , z) - vy.begin();
if(it >= 0 && it < vy.size()){
ans = min(ans , abs(vy[it]-z));
}
it--;
if(it >= 0 && it < vy.size()){
ans = min(ans , abs(vy[it]-z));
}
it--;
if(it >= 0 && it < vy.size()){
ans = min(ans , abs(vy[it]-z));
}
}
return ans;
}
// int main() {
// int N, D, U, Q;
// cin >> N >> D >> U >> Q;
//
// int *F = new int[N];
// for (int i=0; i<N; i++)
// cin >> F[i];
//
// init(N, D, F);
//
// int *A = new int[U], *B = new int[U];
// for (int i=0; i<U; i++) {
// cin >> A[i] >> B[i];
// }
// curseChanges(U, A, B);
//
// for (int i=0; i<Q; i++) {
// int X,Y,V;
// cin >> X >> Y >> V;
// int YourAnswer = question(X,Y,V);
// cout << YourAnswer << "\n";
// }
// return 0;
// }
//
