#include <bits/stdc++.h>
using namespace std;
int n, d;
//vector<int> vh;
vector<int> vhs;
vector<int> vid;
vector<vector<vector<pair<int, int>>>> vnext;
vector<vector<int>> vlast;
vector<vector<int>> id;
void init(int N, int D, int H[]) {
n = N;
d = D;
vhs = vector<int> (N);
vector<pair<int, int>> vq;
for (int i = 0; i < N; i++) {
vhs[i] = H[i];
vq.push_back({vhs[i], i});
}
sort(vhs.begin(), vhs.end());
sort(vq.begin(), vq.end());
vid = vector<int> (n);
for (int i = 0; i < N; i++) {
vid[vq[i].second] = i;
}
vnext = vector<vector<vector<pair<int, int>>>> (n, {{{-1, 1}}, {{-1, -1}}});
vlast = vector<vector<int>> (n, {-1, 0});
id = vector<vector<int>> (n, {-1, n});
}
void rem_friend (int a, int b, int i, vector<map<int, int>> &mv, vector<set<int>> &active, vector<map<int, bool>> &mstate) {
mstate[a][b] = false;
int m = mv[a][b];
int l = vlast[a][m];
int r = vnext[a][m].back().second;
vnext[a][l].push_back({i, r});
vlast[a][r] = l;
active[a].erase(b);
}
void add_friend (int a, int b, int i, vector<map<int, int>> &mv, vector<set<int>> &active, vector<map<int, bool>> &mstate) {
if (mstate[a].count(b) == 0) {
mstate[a][b] = true;
mv[a][b] = vnext[a].size();
vnext[a].push_back({});
vlast[a].push_back(-1);
id[a].push_back(b);
}
mstate[a][b] = true;
auto it = active[a].upper_bound(b);
int r = mv[a][*it];
int l = mv[a][*prev(it)];
int m = mv[a][b];
vnext[a][l].push_back({i, m});
vnext[a][m].push_back({i, r});
vlast[a][m] = l;
vlast[a][r] = m;
active[a].insert(b);
}
void curseChanges(int U, int A[], int B[]) {
vector<map<int, int>> mv (n, {{-1, 0}, {n, 1}});
vector<map<int, bool>> mstate (n);
vector<set<int>> active (n, {-1, n});
for (int i = 0; i < U; i++) {
int a = vid[A[i]];
int b = vid[B[i]];
if (active[a].count(b) != 0) {
// remove friend
rem_friend(a, b, i, mv, active, mstate);
rem_friend(b, a, i, mv, active, mstate);
} else {
add_friend(a, b, i, mv, active, mstate);
add_friend(b, a, i, mv, active, mstate);
}
}
}
int question(int x, int y, int v) {
int x1 = vid[x];
int y1 = vid[y];
int sol = 1e9;
int curl = (--upper_bound(vnext[x1][0].begin(), vnext[x1][0].end(), make_pair(v, -2)))->second;
int curr = (--upper_bound(vnext[y1][0].begin(), vnext[y1][0].end(), make_pair(v, -2)))->second;
while (curl != 1) {
while (curr != 1 && id[y1][(--upper_bound(vnext[y1][curr].begin(), vnext[y1][curr].end(), make_pair(v, -2)))->second] <= id[x1][curl]) {
curr = (--upper_bound(vnext[y1][curr].begin(), vnext[y1][curr].end(), make_pair(v, -2)))->second;
}
if (curr != 1 && curr != 0 && curr != -1) {
int nsol = abs(vhs[id[x1][curl]] - vhs[id[y1][curr]]);
sol = min(sol, nsol);
}
int curr_next = (--upper_bound(vnext[y1][curr].begin(), vnext[y1][curr].end(), make_pair(v, -2)))->second;
if (curr_next != 1 && curr_next != 0 && curr_next != -1) {
int nsol = abs(vhs[id[x1][curl]] - vhs[id[y1][curr_next]]);
sol = min(sol, nsol);
}
curl = (--upper_bound(vnext[x1][curl].begin(), vnext[x1][curl].end(), make_pair(v, -2)))->second;
}
return sol;
}
