#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define emb emplace_back
#define fr first
#define sc second
#define all(x) x.begin(),x.end()
#define sp << " " <<
typedef pair<int,int> ii;
struct Node{
int l,r;
Node(){l=r=0;}
Node(int ll,int rr){l=ll;r=rr;}
};
int sz=0;
vector<Node> tree;
vector<vector<int>> t,v;
vector<int> h,ind;
vector<ii> trust;
int newNode(int l=0,int r=0){
tree.emb(l,r);
return sz++;
}
inline int update(int node,int l,int r,int qx){
if(l==r){
if(node) return 0;
node=newNode();
return node;
}
int mid=(l+r)/2;
if(qx<=mid){
int newL=update(tree[node].l,l,mid,qx);
if(!newL && !tree[node].r) return 0;
else return newNode(newL,tree[node].r);
}
else{
int newR=update(tree[node].r,mid+1,r,qx);
if(!tree[node].l && !newR) return 0;
else return newNode(tree[node].l,newR);
}
}
inline void query(int node1,int node2,int l,int r){
if(!node1 && !node2) return;
if(l==r){
if(node1) trust.pb({h[l],1});
if(node2) trust.pb({h[l],2});
return;
}
int mid=(l+r)/2;
query(tree[node1].l,tree[node2].l,l,mid);
query(tree[node1].r,tree[node2].r,mid+1,r);
}
int n;
void init(int N, int D, int H[]){
newNode();
n=N;
vector<ii> zort;
h.assign(n,0);
ind.assign(n,0);
for(int i=0;i<n;i++){
h[i]=H[i];
zort.emb(h[i],i);
}
sort(all(h));
sort(all(zort));
for(int i=0;i<n;i++)
ind[zort[i].sc]=i;
t.assign(n,vector<int>(1,0));
v.assign(n,vector<int>(1,0));
}
void curseChanges(int U, int A[], int B[]){
for(int i=1;i<=U;i++){
int x=A[i-1],y=B[i-1];
x=ind[x];y=ind[y];
t[x].pb(i);t[y].pb(i);
v[x].pb(update(v[x].back(),0,n-1,y));
v[y].pb(update(v[y].back(),0,n-1,x));
}
}
int question(int x, int y, int T) {
x=ind[x];y=ind[y];
int itl=upper_bound(all(t[x]),T)-t[x].begin()-1;
int itr=upper_bound(all(t[y]),T)-t[y].begin()-1;
trust.clear();
query(v[x][itl],v[y][itr],0,n-1);
int ans=1e9;
for(int i=1;i<(int)trust.size();i++){
if(trust[i].sc!=trust[i-1].sc)
ans=min(ans,trust[i].fr-trust[i-1].fr);
}
return ans;
}
