#include <bits/stdc++.h>
#define FOR(i, a, b) for (auto i = (a); i <= (b); i++)
#define ROF(i, a, b) for (auto i = (a); i >= (b); i--)
using namespace std;
using ll = long long;
const int N = 1e5 + 5, C = 50;
int h[N];
bool seen[N];
set<int> cur[N];
vector<array<int, 3>> upds[N];
vector<vector<int>> adj[N];
void upd(int x, int y, int d) {
if (cur[x].count(y)) {
cur[x].erase(y);
upds[x].push_back({d, y, -1});
} else {
cur[x].insert(y);
upds[x].push_back({d, y, 1});
}
if (upds[x].size() % C == 0) {
adj[x].push_back({});
for (int y : cur[x])
adj[x].back().push_back(y);
}
}
void init(int n, int d, int _h[]) {
copy(_h, _h + n, h);
}
void curseChanges(int U, int A[], int B[]) {
FOR(i, 0, U - 1)
upd(A[i], B[i], i),
upd(B[i], A[i], i);
}
vector<int> get(int x, int d) {
int n = lower_bound(upds[x].begin(), upds[x].end(), array<int, 3>{d, -1, -1}) - upds[x].begin();
vector<int> ans;
ROF(i, n - 1, n / C * C) {
auto [_, y, z] = upds[x][i];
if (!seen[y]) {
seen[y] = 1;
if (z == 1)
ans.push_back(h[y]);
}
}
if (n >= C)
for (int y : adj[x][n / C - 1])
if (!seen[y])
ans.push_back(h[y]);
FOR(i, n / C * C, n - 1) seen[upds[x][i][1]] = 0;
return ans;
};
int question(int x, int y, int d) {
auto hx = get(x, d);
auto hy = get(y, d);
sort(hx.begin(), hx.end());
sort(hy.begin(), hy.end());
int nx = hx.size(), ny = hy.size(), j = -1, ans = 1e9;
FOR(i, 0, nx - 1) {
while (j + 1 < ny && hy[j + 1] <= hx[i]) j++;
if (j >= 0) ans = min(ans, hx[i] - hy[j]);
if (j + 1 < ny) ans = min(ans, hy[j + 1] - hx[i]);
}
return ans;
}
