#include <bits/stdc++.h>
using namespace std;
void __print(int x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << "'" << x << "'";}
void __print(const char *x) {cerr << '"' << x << '"';}
void __print(const string &x) {cerr << '"' << x << '"';}
void __print(bool x) {cerr << (x ? "true" : "false");}
template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ", "; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? ", " : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifdef LOCAL
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif
typedef pair<int, int> T;
const int oo2 = 1e9;
int n, d;
vector<int>h;
vector<T>edges, life;
void init(int _n, int _d, int H[]){
n = _n; d = _d;
h.resize(n);
for (int i = 0; i<n; i++) h[i] = H[i];
}
int sz = 1;
vector<vector<T>>tab;
void init(int s){
while (sz < s) sz*=2;
tab.resize(2*sz);
}
void update(int x, int lx, int rx, int i){
if (lx > life[i].second || rx < life[i].first) return;
if (lx >= life[i].first && rx <= life[i].second) {
for (int rep = 0; rep < 2; rep++){
tab[x].emplace_back(edges[i]);
swap(edges[i].first, edges[i].second);
}
return;
}
int m = (lx+rx)/2;
update(2*x, lx, m, i);
update(2*x+1, m+1, rx, i);
}
void curseChanges(int u, int A[], int B[]){
map<T, int>alive;
for (int i = 0; i<u; i++){
if (A[i] > B[i]) swap(A[i], B[i]);
if (alive.find({A[i], B[i]}) == alive.end()){
alive[{A[i], B[i]}] = i+1;
} else {
edges.emplace_back(A[i], B[i]);
life.emplace_back(alive[{A[i], B[i]}], i);
alive.erase({A[i], B[i]});
}
}
for (auto [v, i]: alive){
edges.emplace_back(v);
life.emplace_back(i, u);
}
init(u+1);
debug(edges);
debug(life);
for (int i = 0; i<(int)life.size(); i++){
update(1, 0, sz-1, i);
}
for (int i = 1; i<2*sz; i++){
sort(tab[i].begin(), tab[i].end());
}
}
void find(int x, int lx, int rx, int pos, int v, vector<T>&curr){
//z wierzcholka x
int L = (int)(lower_bound(tab[x].begin(), tab[x].end(), T{v, 0}) - tab[x].begin());
for (int rep = L; rep < (int)tab[x].size(); rep++){
if (tab[x][rep].first != v) break;
curr.emplace_back(h[tab[x][rep].second], v);
}
if (lx == rx) return;
int m = (lx+rx)/2;
if (pos <= m) find(2*x, lx, m, pos, v, curr);
else find(2*x+1, m+1, rx, pos, v, curr);
};
int question(int x, int y, int v){
vector<T>X;
find(1, 0, sz-1, v, x, X);
find(1, 0, sz-1, v, y, X);
debug(X);
sort(X.begin(), X.end());
int ans = oo2;
for (int i = 1; i<(int)X.size(); i++){
if (X[i].second != X[i-1].second) {
ans = min(ans, X[i].first-X[i-1].first);
}
}
return ans;
}
