#include <bits/stdc++.h>
using namespace std;
struct segTree{
struct node{
unordered_map<int,vector<int>>mp;
};
node *st;
segTree(int n){
int x = ceil(log2(n));
x++;
st = new node[(1<<x)];
}
void reset(int n){
delete[] st;
int x = ceil(log2(n));
x++;
st = new node[(1<<x)];
}
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].mp[x].push_back(y);
st[ind].mp[y].push_back(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[]){
if(st[ind].mp.find(x)!=st[ind].mp.end()){
for(int i : st[ind].mp[x]){
sx.push_back(h[i]);
}
}
if(st[ind].mp.find(y)!=st[ind].mp.end()){
for(int i : st[ind].mp[y]){
sy.push_back(h[i]);
}
}
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[]) {
st.reset(mxu);
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]);
}
}
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));
}
}
}
return ans;
}
