#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int INF = 1e9;
const int MOD = 1e9 + 7;
int H[200002], N, lg2[200002];
struct interval {
int l, r, ind;
bool operator < (const interval &other) {
return l < other.l;
}
};
vector<interval>v[200002];
void init (int n, int d, int h[]) {
N = n;
for (int i = 1; i <= n; i++)
H[i] = h[i - 1];
}
vector<vector<int>>rmq[200002];
int uwu;
void curseChanges(int U, int A[], int B[]) {
uwu = U;
map<pair<int, int>, int>mp;
for (int i = 0; i < U; i++) {
A[i]++;
B[i]++;
if (A[i] > B[i])
swap(A[i], B[i]);
if (mp[{A[i], B[i]}] == 0) {
mp[{A[i], B[i]}] = i + 1;
}
else {
v[A[i]].push_back({mp[{A[i], B[i]}], i + 1, B[i]});
v[B[i]].push_back({mp[{A[i], B[i]}], i + 1, A[i]});
mp[{A[i], B[i]}] = 0;
}
}
for (auto it : mp) {
if (it.second) {
v[it.first.first].push_back({it.second, U + 1, it.first.second});
v[it.first.second].push_back({it.second, U + 1, it.first.first});
}
}
for (int i = 1; i <= N; i++)
sort(v[i].begin(), v[i].end());
for (int i = 2; i <= U; i++)
lg2[i] = lg2[i / 2] + 1;
for (int i = 1; i <= N; i++) {
int k = lg2[v[i].size()];
rmq[i].resize(k + 1);
for (int j = 0; j <= k; j++)
rmq[i][j].resize(v[i].size());
for (int j = 0; j < v[i].size(); j++)
rmq[i][0][j] = j;
for (int j = 1; j <= k; j++)
for (int p = 0; p + (1 << j) - 1 < v[i].size(); p++) {
int ind1 = rmq[i][j - 1][p];
int ind2 = rmq[i][j - 1][p + (1 << (j - 1))];
if (v[i][ind1].r > v[i][ind2].r)
rmq[i][j][p] = ind1;
else
rmq[i][j][p] = ind2;
}
}
}
vector<int> ans;
int query (int shaman, int st, int dr) {
int l = lg2[dr - st + 1];
if (v[shaman][rmq[shaman][l][st]].r > v[shaman][rmq[shaman][l][dr - (1 << l) + 1]].r)
return rmq[shaman][l][st];
else
return rmq[shaman][l][dr - (1 << l) + 1];
}
void rec(int shaman, int st, int dr, int day) {
if (st > dr)
return;
int ind = query(shaman, st, dr);
if (v[shaman][ind].r > day)
ans.push_back(H[v[shaman][ind].ind]);
else
return;
rec(shaman, st, ind - 1, day);
rec(shaman, ind + 1, dr, day);
}
vector<int> find_list (int shaman, int day) {
int st = 0, dr = v[shaman].size() - 1, lim = -1;
while (st <= dr) {
int mid = (st + dr) / 2;
if (v[shaman][mid].l <= day) {
lim = mid;
st = mid + 1;
}
else
dr = mid - 1;
}
ans.clear();
rec(shaman, 0, lim, day);
return ans;
}
int question (int X, int Y, int day) {
X++;
Y++;
vector<int> D1 = find_list(X, day);
vector<int> D2 = find_list(Y, day);
sort(D1.begin(), D1.end());
sort(D2.begin(), D2.end());
int j = 0;
int ans = INF;
for (int i = 0; i < D1.size(); i++) {
while (j < D2.size() && D2[j] < D1[i])
j++;
if (j < D2.size())
ans = min(ans, D2[j] - D1[i]);
if (j > 0)
ans = min(ans, D1[i] - D2[j - 1]);
}
return ans;
}
