#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int N = 8e5+10;
const int INF = 1e9;
int n, d, h[N], a[N], b[N], c;
vector<pii> T[N];
void init(int _n, int _d, int _h[]) {
n=_n, d=_d;
for (int i=0; i<n; ++i) h[i]=_h[i];
}
void add(int v, int l, int r, int ql, int qr, int x, int y) {
if (l > qr || r < ql) return;
if (l >= ql && r <= qr) {
T[v].push_back({x, h[y]});
T[v].push_back({y, h[x]});
return;
} int m=(l+r)/2;
add(2*v, l, m, ql, qr, x, y), add(2*v+1, m+1, r, ql, qr, x, y);
}
void curseChanges(int sz, int _a[], int _b[]) {
c=sz;
map<pii, vector<int>> idx;
for (int i=1; i<=c; ++i) {
a[i]=_a[i-1], b[i]=_b[i-1];
if (a[i] > b[i]) swap(a[i], b[i]);
idx[{a[i], b[i]}].push_back(i);
}
for (auto u : idx) {
u.second.push_back(c+1);
int sz=u.second.size();
// [x0, x1, ..., xn]
for (int i=0; i+1<sz; i+=2) {
add(1, 1, c, u.second[i], u.second[i+1]-1, u.first.first, u.first.second);
}
}
for (int i=0; i<N; ++i) sort(T[i].begin(), T[i].end());
}
void dfs(int v, int l, int r, int p, int x, vector<int> *h) {
int i=upper_bound(T[v].begin(), T[v].end(), make_pair(x, -1))-T[v].begin();
for (int j=i; j<(int)T[v].size(); ++j) {
if (T[v][j].first != x) break;
h->push_back(T[v][j].second);
}
if (l == r) return;
int m=(l+r)/2;
if (p <= m) dfs(2*v, l, m, p, x, h);
else dfs(2*v+1, m+1, r, p, x, h);
}
int fnd(vector<int> a, vector<int> b) {
if (a.empty() || b.empty()) return INF;
int ptr=0, ans=INF;
for (auto u : a) {
while (ptr < (int)b.size()) {
if (b[ptr] <= u) ++ptr;
else break;
}
ans=min(ans, abs(u-b[min((int)b.size()-1, ptr)]));
if (ptr > 0) ans=min(ans, abs(u-b[ptr-1]));
} return ans;
}
int question(int x, int y, int v) {
vector<int> hx, hy;
dfs(1, 1, c, v, x, &hx);
dfs(1, 1, c, v, y, &hy);
sort(hx.begin(), hx.end()), sort(hy.begin(), hy.end());
return fnd(hx, hy);
}
