// #pragma GCC optimize("O3,Ofast,unroll-loops")
// #pragma GCC target("avx2,bmi,popcnt")
#include <bits/stdc++.h>
#define lli long long int
#define ld long double
#define REP(i, n) for(int i = 0; (i) < (n); (i)++)
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define pb push_back
#define MP make_pair
using namespace std;
void fastio() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
}
const int N = 1e5 + 5;
const int MXU = 2e5 + 5;
const int INF = 1e9;
const int MOD = 1e9 + 7;
const int C = 50;
int n, d;
array<vector<array<int, 2> >, N> upd;
array<vector<vector<int> >, N> lst;
array<int, N> h;
void init(int N, int D, int H[]) {
n = N, d = D;
REP(i, n) h[i] = H[i];
}
void make_upd(vector<int> &vec, vector<int> &us) {
sort(all(us));
vector<int> tmp;
int i = 0, j = 0;
auto push = [&tmp](int x) {
if(tmp.size() && tmp.back() == x) tmp.pop_back();
else tmp.pb(x);
};
while(i < vec.size() || j < us.size()) {
if(i >= vec.size()) {
push(us[j]);
j++;
}
else if(j >= us.size()) {
push(vec[i]);
i++;
}
else if(vec[i] < us[j]) {
push(vec[i]);
i++;
}
else {
push(us[j]);
j++;
}
}
swap(tmp, vec);
}
void upd_int(vector<int> &vec, int node, int v) {
int r = (int)(upper_bound(all(upd[node]), array<int,2>({v, INF})) - upd[node].begin());
if(r == 0) {
vec = vector<int>();
return;
}
r--;
r /= C;
vec = lst[node][r];
r *= C;
int ind = r;
vector<int> us;
for(; ind < upd[node].size() && upd[node][ind][0] <= v; ind++) {
us.pb(upd[node][ind][1]);
}
make_upd(vec, us);
}
void curseChanges(int U, int A[], int B[]) {
REP(i, U) {
upd[A[i]].pb({i + 1, B[i]});
upd[B[i]].pb({i + 1, A[i]});
}
for(int node = 0; node < N; node++) {
lst[node].pb(vector<int>());
int last = 0;
for(int j = C; j < upd[node].size(); j += C) {
vector<int> us;
for(int i = last; i < j; i++) {
us.pb(upd[node][i][1]);
}
lst[node].pb(lst[node].back());
make_upd(lst[node][(int)lst[node].size() - 1], us);
last = j;
}
}
}
auto comp = [](int x, int y) {
return h[x] < h[y];
};
int question(int x, int y, int v) {
vector<int> lstx, lsty;
upd_int(lstx, x, v);
upd_int(lsty, y, v);
sort(all(lstx), comp);
sort(all(lsty), comp);
int ret = INF;
int i = 0, j = 0;
// cout << "lstx: ";
// for(auto c: lstx) {
// cout << c << " ";
// }
// cout << "\n";
// cout << "lsty: ";
// for(auto c: lsty) {
// cout << c << " ";
// }
// cout << "\n";
while(i < lstx.size() && j < lsty.size()) {
ret = min(ret, abs(h[lstx[i]] - h[lsty[j]]) );
if(h[lstx[i]] < h[lsty[j]]) {
i++;
}
else {
j++;
}
}
return ret;
}
