#pragma GCC optimize("Ofast","unroll-loops")
#include <bits/stdc++.h>
using namespace std;
namespace {
const int threshold = 6; // Can change
vector<vector<pair<int,int>>> updates;
vector<vector<pair<int,vector<int>>>> blocks;
vector<int> h;
int N;
}
void init(int N, int D, int H[]) {
updates.resize(N);
::N = N;
blocks.resize(N);
h.resize(N);
for(int i=0;i<N;i++){
h[i]=H[i];
blocks[i].emplace_back(0,vector<int>());
}
}
void curseChanges(int U, int A[], int B[]) {
vector<set<int>> curr(N);
vector<int> currUpdates(N);
for(int i=0;i<U;i++){
// Process A->B
int upd = B[i];
if(curr[A[i]].count(B[i])){
upd=-upd-1;curr[A[i]].erase(B[i]);
} else {
curr[A[i]].insert(B[i]);
}
// updates[A[i]].emplace_back(i+1,upd);
// if(++currUpdates[A[i]] == threshold){
// currUpdates[A[i]]=0;
// blocks[A[i]].emplace_back(i+1,vector<int>());
// for(int j:curr[A[i]])blocks[A[i]].back().second.emplace_back(j);
// }
// Process B->A
upd = A[i];
if(curr[B[i]].count(A[i])){
upd=-upd-1;curr[B[i]].erase(A[i]);
} else {
curr[B[i]].insert(A[i]);
}
// updates[B[i]].emplace_back(i+1,upd);
// if(++currUpdates[B[i]] == threshold){
// currUpdates[B[i]]=0;
// blocks[B[i]].emplace_back(i+1,vector<int>());
// for(int j:curr[B[i]])blocks[B[i]].back().second.emplace_back(j);
// }
}
// SUBTASK 3
for(int i=0;i<N;i++){
currUpdates[i]=0;
blocks[i].emplace_back(U,vector<int>());
for(int j:curr[i])blocks[i].back().second.emplace_back(j);
}
}
int question(int x, int y, int v) {
auto recover = [&](int curr){
auto base = --upper_bound(blocks[curr].begin(),blocks[curr].end(),v,[](const int& a,const pair<int,vector<int>>& b){return a<b.first;});
int st = base->first;
set<int> ans(base->second.begin(),base->second.end());
// auto iter = upper_bound(updates[curr].begin(),updates[curr].end(),st,[](const int& a,const pair<int,int>& b){return a<b.first;});
// while(iter!=updates[curr].end() and iter->first <=v){
// int upd = iter->second;
// if(upd<0){
// upd= -upd-1;
// ans.erase(upd);
// } else ans.insert(upd);
// iter++;
// }
vector<int> heights;
for(int i:ans)heights.emplace_back(h[i]);
sort(heights.begin(),heights.end());
return heights;
};
auto htX = recover(x);
auto htY = recover(y);
auto f = htX.begin();
auto s = htY.begin();
int ans = 1e9;
while(f!=htX.end() and s!=htY.end()){
ans = min(ans,abs((*f)-(*s)));
if(*f < *s)f++;
else s++;
}
return ans;
}
