#include <bits/stdc++.h>
typedef int ll;
#define FOR(i,x,y) for(ll i=x; i<y; i++)
#define FORNEG(i,x,y) for(ll i=x; i>y; i--)
using namespace std;
ll h[100001];
struct cmp {
bool operator() (ll a, ll b) const {
if (h[a] == h[b]) return a<b;
return h[a] < h[b];
}
};
vector<array<ll,2>> changes[100001];
vector<set<ll, cmp>> lotchange[100001];
void init(int N, int D, int H[]) {
FOR(i,0,N) h[i] = H[i];
}
void curseChanges(int U, int A[], int B[]) {
set<ll, cmp> tempedges[100001];
FOR(i,0,U){
if (tempedges[A[i]].find(B[i]) != tempedges[A[i]].end()){
changes[A[i]].push_back({i, B[i]});
tempedges[A[i]].erase(B[i]);
}
else{
changes[A[i]].push_back({i, B[i]});
tempedges[A[i]].insert(B[i]);
}
if (tempedges[B[i]].find(A[i]) != tempedges[B[i]].end()){
changes[B[i]].push_back({i, A[i]});
tempedges[B[i]].erase(A[i]);
}
else{
changes[B[i]].push_back({i, A[i]});
tempedges[B[i]].insert(A[i]);
}
if ((changes[A[i]].size()-1)%50==0){
lotchange[A[i]].push_back(tempedges[A[i]]);
}
if ((changes[B[i]].size()-1)%50==0){
lotchange[B[i]].push_back(tempedges[B[i]]);
}
}
}
int mindiff(set<ll, cmp>&a, set<ll, cmp>&b){
ll ans = 1000000000;
basic_string<ll> A,B;
for (auto&i : a) A.push_back(h[i]);
for (auto&i : b) B.push_back(h[i]);
ll l=0,r=0;
while (l<A.size() && r<B.size()){
ans = min(ans, abs(A[l] - B[r]));
if (A[l] < B[r]) l++;
else r++;
}
return ans;
return ans;
}
int question(int x, int y, int v) {
v--;
ll ans = 1000000000;
ll pos = upper_bound(changes[x].begin(), changes[x].end(), array<ll, 2>{v, 1000000000})-changes[x].begin();
pos--;
set<ll, cmp> X;
if (pos >= 0){
X=lotchange[x][pos/50];
FOR(i, (pos/50)*50+1, pos+1){
ll temp = changes[x][i][1];
if (X.find(temp) != X.end()) X.erase(temp);
else X.insert(temp);
}
}
pos = upper_bound(changes[y].begin(), changes[y].end(), array<ll, 2>{v, 1000000000})-changes[y].begin();
pos--;
set<ll, cmp> Y;
if (pos >= 0){
Y=lotchange[y][pos/50];
FOR(i, (pos/50)*50+1, pos+1){
ll temp = changes[y][i][1];
if (Y.find(temp) != Y.end()) Y.erase(temp);
else Y.insert(temp);
}
}
return mindiff(X,Y);
}
