#include <bits/stdc++.h>
using namespace std;
struct segTree{
vector<array<int,2>> *st;
segTree(int n){
int x = ceil(log2(n));
x++;
st = new vector<array<int,2>>[(1<<x)];
}
void fix(int l, int r, int ind){
sort(st[ind].begin(),st[ind].end());
if(l==r)
return;
int mid = (l+r)/2;
fix(l,mid,ind*2+1);
fix(mid+1,r,ind*2+2);
}
void update(int l, int r, int s, int e, int ind, int x, int y){
if(e<l||s>r){
return;
}
if(s<=l&&r<=e){
st[ind].push_back({x,y});
st[ind].push_back({y,x});
return;
}
int mid = (l+r)/2;
update(l,mid,s,e,ind*2+1,x,y);
update(mid+1,r,s,e,ind*2+2,x,y);
}
void query(int l, int r, int i, int ind, int x, int y, vector<int>&sx, vector<int>&sy, int h[]){
array<int,2>temp = {x,-1};
auto it = lower_bound(st[ind].begin(),st[ind].end(),temp);
while(it!=st[ind].end()&&(*it)[0]==x){
sx.push_back(h[(*it)[1]]);
it++;
}
temp={y,-1};
it = lower_bound(st[ind].begin(),st[ind].end(),temp);
while(it!=st[ind].end()&&(*it)[0]==y){
sy.push_back(h[(*it)[1]]);
it++;
}
if(l==r)
return;
int mid = (l+r)/2;
if(i<=mid){
query(l,mid,i,ind*2+1,x,y,sx,sy,h);
}
else{
query(mid+1,r,i,ind*2+2,x,y,sx,sy,h);
}
}
};
int mxu = 2e5+5;
segTree st(mxu);
const int mxn = 1e5+5;
int h[mxn];
void init(int N, int D, int H[]) {
for(int i = 0;i<N;i++){
h[i]=H[i];
}
}
void curseChanges(int U, int A[], int B[]) {
set<array<int,3>>s;
for(int i = 0;i<U;i++){
int a,b;
a=A[i];
b=B[i];
if(a>b){
swap(a,b);
}
auto it = (s.lower_bound({a,b,-1}));
if(it!=s.end()&&(*it)[0]==a&&(*it)[1]==b){
///stop trust
st.update(0,mxu,(*it)[2]+1,i,0,a,b);
s.erase(it);
}
else{
///begin
s.insert({a,b,i});
}
}
for(array<int,3>a:s){
st.update(0,mxu,a[2]+1,mxu,0,a[0],a[1]);
}
st.fix(0,mxu,0);
}
int question(int x, int y, int d) {
vector<int>xarr,yarr;
st.query(0,mxu,d,0,x,y,xarr,yarr,h);
sort(xarr.begin(),xarr.end());
int ans = 1e9;
if(xarr.size()){
for(int i : yarr){
auto it = lower_bound(xarr.begin(),xarr.end(),i);
if(it!=xarr.end()){
ans=min(ans,(*it)-i);
}
if(it!=xarr.begin()){
it--;
ans=min(ans,i-(*it));
}
}
}
xarr.clear();
yarr.clear();
return ans;
}
