#include <vector>
#include <iostream>
#include <algorithm>
#include <set>
using namespace std;
/*
Save neighbour list by node, reduce storage space by constant factor (DIF)
Made for your by Mate Busa
*/
const int INF = 1000000000;
const int DIF = 50; //other numbers would also work, but i like this number
int NN, cur, goes, last, place, vv, a, b, ans;
int HH[100000];
int who[2][DIF];
int step[2];
int id[2];
int num[2];
int st[2];
int p[2][100000];
bool in[100000];
bool out[2][100000];
struct point{
int a, day, id;
bool in;
};
vector<pair<int,int> > change[100000];
vector<point> update[100000];
vector<pair<int,int> > vec[400000];
set<pair<int,int> > szet;
int news[2][DIF];
void init(int N, int D, int H[]) {
NN = N; cur = 1;
for(int i=0; i<N; i++) HH[i] = H[i];
}
void curseChanges(int U, int A[], int B[]) {
for(int i=0; i<U; i++) {
change[A[i]].push_back({B[i],i+1});
change[B[i]].push_back({A[i],i+1});
}
for(int i=0; i<NN; i++){
update[i].resize(change[i].size()+1); update[i][0].day = 0; update[i][0].id = 0; goes = 1;
szet.clear();
for(pair<int,int> j:change[i]){
in[j.first] = !in[j.first];
update[i][goes].in = in[j.first];
update[i][goes].a = j.first;
update[i][goes].day = j.second;
if(in[j.first]){
szet.insert({HH[j.first],j.first});
} else {
szet.erase({HH[j.first],j.first});
}
if(goes%DIF==0){
vec[cur].resize(szet.size()); place = 0;
for(pair<int,int> k:szet) vec[cur][place++] = k;
update[i][goes].id = cur++;
} else {
update[i][goes].id = -1;
}
goes++;
}
for(pair<int,int> j:szet) in[j.second] = false;
}
}
int bi(int x, int y){
if(x==y) return x;
int fel = (x+y+1)/2;
if(update[place][fel].day<=vv) return bi(fel,y);
return bi(x,fel-1);
}
void choose(int x, int y){
place = x; place = bi(0,update[x].size()-1);
step[y] = 0; num[y] = 0;
while(update[x][place].id==-1){
a = update[x][place].a;
if(!in[a]){
in[a] = true;
if(update[x][place].in){
news[y][num[y]++] = HH[a];
} else {
out[y][a] = true;
}
}
who[y][step[y]++] = a;
place--;
}
sort(news[y],news[y]+num[y]);
for(int i=0; i<step[y]; i++) {in[who[y][i]] = false;}
id[y] = update[x][place].id;
}
int question(int x, int y, int v) {
vv = v;
choose(x,0); choose(y,1);
ans = INF;
for(int i=0; i<2; i++){
int aa = 0, bb = 0; st[i] = 0;
while(aa<vec[id[i]].size() || bb<num[i]){
if(aa==vec[id[i]].size()){
p[i][st[i]++] = news[i][bb++];
} else if(bb==num[i]){
if(!out[i][vec[id[i]][aa].second]) p[i][st[i]++] = vec[id[i]][aa].first;
aa++;
} else if(vec[id[i]][aa].first<news[i][bb]){
if(!out[i][vec[id[i]][aa].second]) p[i][st[i]++] = vec[id[i]][aa].first;
aa++;
} else {
p[i][st[i]++] = news[i][bb++];
}
}
}
int g = 0;
for(int i=0; i<st[0]; i++){
while(g<st[1] && p[1][g]<p[0][i]){
ans = min(ans,p[0][i] - p[1][g++]);
}
if(g==st[1]) break;
ans = min(ans,p[1][g] - p[0][i]);
}
for(int i=0; i<2; i++){
for(int j=0; j<step[i]; j++) out[i][who[i][j]] = false;
}
return ans;
}
