// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>
using namespace std;
#define nl '\n'
#define pb push_back
#define sz(x) int(x.size())
#define f first
#define s second
#define mp make_pair
using pi = pair<int, int>;
template<class T> using V = vector<T>;
using vi = V<int>;
using vpi = V<pi>;
const int nax = (1 << 18);
const int INF = 1e9;
vpi seg[2 * nax];
int N, D; vi H;
void init(int n, int d, int h[]) {
N = n, D = d; H = vi(N);
for(int i = 0; i < N; i++) H[i] = h[i];
// cout << "INIT" << endl;
}
void ae(int x, pi e) {
seg[x].pb(e);
swap(e.f, e.s);
seg[x].pb(e);
}
void add(int l, int r, const pi &e) {
for(l += nax, r += nax + 1; l < r; l /= 2, r /= 2) {
if (l & 1) ae(l++, e);
if (r & 1) ae(--r, e);
}
}
vi get(int p, int x) {
vi adj; for(p += nax; p; p /= 2) {
int pos = lower_bound(begin(seg[p]), end(seg[p]), mp(x, -1)) - begin(seg[p]);
while(pos < sz(seg[p])) {
if (seg[p][pos].f == x) adj.pb(H[seg[p][pos].s]);
pos++;
}
}
return adj;
}
void curseChanges(int m, int a[], int b[]) {
map<pi, int> L;
for(int i = 0; i < m; i++) {
pi e = minmax(a[i], b[i]);
if (L.find(e) == L.end()) L[e] = i + 1;
else {
add(L[e], i, e);
L.erase(e);
}
}
for(auto& e : L) {
add(e.s, m, e.f);
}
for(int i = 1; i < 2 * nax; i++) sort(begin(seg[i]), end(seg[i]));
// cout << "UPDATES" << endl;
}
int question(int x, int y, int v) {
// cout << "QRY: " << x << " " << y << " " << v << endl;
vi hx = get(v, x), hy = get(v, y);
sort(begin(hx), end(hx)); sort(begin(hy), end(hy));
// for(auto& h : hx) cout << h << " ";
// cout << endl;
// for(auto& h : hy) cout << h << " ";
// cout << endl;
int ans = INF;
for(int i = 0, j = 0; i < sz(hx); i++) {
while(j < sz(hy) && hx[i] > hy[j]) j++;
if (j < sz(hy)) ans = min(ans, hy[j] - hx[i]);
if (j) ans = min(ans, hx[i] - hy[j - 1]);
}
return ans;
}
// Breathe In, Breathe Out
