#include <bits/stdc++.h>
#define all(a) a.begin(), a.end()
using namespace std;
typedef pair<int, int> pii;
const int C = 40;
struct checkpoint {
int time;
vector<int> guys;
checkpoint() {}
checkpoint(int T, vector<int> sett) {
time = T;
guys = sett;
}
bool operator<(const checkpoint &a) const {return time < a.time;}
};
int n, d, u;
vector<int> heights;
vector<pii> changes;
int min_dist(vector<int> first, vector<int> second) {
if (first.empty() || second.empty())
return 1e9;
for (int i = 0; i < first.size(); i++)
first[i] = heights[first[i]];
for (int i = 0; i <second.size(); i++)
second[i] = heights[second[i]];
sort(all(first));
sort(all(second));
int pnt1 = 0, pnt2 = 0, out = 2e9;
while (pnt1 < first.size() and pnt2 < second.size()) {
out = min(out, abs(first[pnt1] - second[pnt2]));
if (pnt1 + 1 == first.size())
pnt2++;
else if (pnt2 + 1 == second.size())
pnt1++;
else if (first[pnt1] < second[pnt2])
pnt1++;
else
pnt2++;
}
return out;
}
vector<vector<checkpoint> > states;
vector<vector<pii> > individ_updates;
void init(int N, int D, int H[]) {
n = N;
individ_updates.resize(n);
states.resize(n);
heights.resize(N);
for (int i = 0; i < n; i++)
{
heights[i] = H[i];
states[i].push_back(checkpoint(-1, vector<int>()));
}
d = D;
states.resize(n);
}
void process(set<int> &set, int &val) {
if (set.count(val))
set.erase(val);
else
set.insert(val);
}
void curseChanges(int U, int A[], int B[]) {
u = U;
changes.resize(u);
for (int i = 0; i < u; i++)
{
changes[i].first = A[i], changes[i].second = B[i];
individ_updates[A[i]].push_back({i, B[i]});
individ_updates[B[i]].push_back({i, A[i]});
}
vector<int> time_since_last(n, 0);
vector<set<int> > guys(n);
for (int i = 0; i < u; i++) {
int a = changes[i].first, b = changes[i].second;
process(guys[a], b);
process(guys[b], a);
if (time_since_last[a] == C) {
states[a].push_back(checkpoint(i, vector<int>(all(guys[a]))));
time_since_last[a] = 0;
}
if (time_since_last[b] == C) {
states[b].push_back(checkpoint(i, vector<int>(all(guys[b]))));
time_since_last[b] = 0;
}
time_since_last[a]++;
time_since_last[b]++;
}
}
// todo; finish get set
vector<int> get_set(int x, int v) {
checkpoint check = *prev(upper_bound(all(states[x]), checkpoint(v, vector<int>())));
set<int> guys(all(check.guys));
int idx = lower_bound(all(individ_updates[x]), pii(check.time, 1e9)) - individ_updates[x].begin();
for (; idx < individ_updates[x].size() and individ_updates[x][idx].first < v; idx++)
process(guys, individ_updates[x][idx].second);
return vector<int>(all(guys));
}
int question(int x, int y, int v) {
vector<int> x_set = get_set(x, v), y_set = get_set(y, v);
return min_dist(x_set, y_set);
}
