#include<bits/stdc++.h>
#include "grader.cpp"
using namespace std;
const int N = 2e5 + 100;
int n, D, H[N];
int U, A[N], B[N];
void init(int NN, int DD, int HH[]) {
n = NN;
D = DD;
for(int i = 0; i < n; i++)
H[i] = HH[i];
}
vector<pair<int, int>> t[N];
void upd(int x, int l, int r, int tl, int tr, int a, int b)
{
// cout << x << ' ' << l << ' ' << r << ' ' << tl << ' ' << tr << ' ' << a << ' ' << b << '\n';
// getchar();
if(tl <= l && tr >= r)
{
t[x].push_back({a, b});
t[x].push_back({b, a});
return;
}
if(tl > r || tr < l)
return;
int m = (l + r) / 2;
upd(x * 2, l, m, tl, tr, a, b);
upd(x * 2 + 1, m + 1, r, tl, tr, a, b);
}
vector<int> V1, V2;
vector<int> G1, G2;
void add(int x, int a, int b)
{
int ind = lower_bound(t[x].begin(), t[x].end(), make_pair(a, 0)) - t[x].begin();
for(int i = ind; i < t[x].size(); i++)
{
if(t[x][i].first != a)
break;
G1.push_back(t[x][i].second);
V1.push_back(H[t[x][i].second]);
}
ind = lower_bound(t[x].begin(), t[x].end(), make_pair(b, 0)) - t[x].begin();
for(int i = ind; i < t[x].size(); i++)
{
if(t[x][i].first != b)
break;
G2.push_back(t[x][i].second);
V2.push_back(H[t[x][i].second]);
}
}
void get(int x, int l, int r, int ind, int a, int b)
{
add(x, a, b);
if(l == r)
return;
int m = (l + r) / 2;
if(ind <= m)
get(x * 2, l, m, ind, a, b);
else
get(x * 2 + 1, m + 1, r, ind, a, b);
}
void out(int x, int l, int r)
{
cout << l << ' ' << r << " == " << '\n';
for(auto i : t[x])
cout << i.first << ' ' << i.second << '\n';
cout << "\n\n";
if(l == r)
return;
int m = (l + r) / 2;
out(x * 2, l, m);
out(x * 2 + 1, m + 1, r);
}
void curseChanges(int u, int AA[], int BB[]) {
for(int i = 0; i < u; i++)
{
A[i + 1] = AA[i];
B[i + 1] = BB[i];
}
U = u;
map<pair<int, int>, int> mp;
for(int i = 1; i <= u; i++)
{
if(mp[{A[i], B[i]}] != 0)
{
int ind = mp[{A[i], B[i]}];
upd(1, 1, u, ind, i - 1, A[i], B[i]);
mp[{A[i], B[i]}] = mp[{B[i], A[i]}] = 0;
}
else
mp[{A[i], B[i]}] = mp[{B[i], A[i]}] = i;
}
for(auto i : mp)
{
if(i.second == 0 || i.first.first > i.first.second)
continue;
upd(1, 1, u, i.second, u, i.first.first, i.first.second);
}
for(int i = 1; i <= u * 4; i++)
sort(t[i].begin(), t[i].end());
}
int question(int x, int y, int v) {
V1.clear();
V2.clear();
G1.clear();
G2.clear();
get(1, 1, U, v, x, y);
sort(V1.begin(), V1.end());
sort(V2.begin(), V2.end());
if(V1.empty() || V2.empty())
return 1e9;
long long res = 2e9;
for(auto i : V1)
{
int ind = lower_bound(V2.begin(), V2.end(), i) - V2.begin();
if(ind != V2.size())
res = min(res, 1ll * V2[ind] - i);
if(ind)
res = min(res, 1ll * i - V2[ind - 1]);
}
// cout << res << "\n";
// for(auto i : V1)
// cout << i << " ";
// cout << '\n';
// for(auto i : V2)
// cout << i << ' ';
// exit(0);
return res;
}
