#include <bits/stdc++.h>
using namespace std;
namespace {
const int threshold = 10; // Can change
vector<vector<pair<int,int>>> updates(100000);
vector<vector<pair<int,vector<int>>>> blocks(100000);
vector<int> h(100000);
int N;
}
void flip(vector<int> &a,int x){
int ok = -1, empty=-1;
for(int i=0;i<a.size();i++){
if(a[i]==-1)empty=i;
else if(a[i]==x){ok=1;a[i]=-1;break;}
}
if(ok==-1){
if(empty==-1)a.emplace_back(x);
else a[empty]=x;
}
}
void init(int N, int D, int H[]) {
::N = 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<vector<int>> curr(N);
vector<int> currUpdates(N);
for(int i=0;i<U;i++){
// Process A->B
flip(curr[A[i]],B[i]);
updates[A[i]].emplace_back(i+1,B[i]);
if(++currUpdates[A[i]] == threshold){
currUpdates[A[i]]=0;
blocks[A[i]].emplace_back(i+1,curr[A[i]]);
}
// Process B->A
flip(curr[B[i]],A[i]);
updates[B[i]].emplace_back(i+1,A[i]);
if(++currUpdates[B[i]] == threshold){
currUpdates[B[i]]=0;
blocks[B[i]].emplace_back(i+1,curr[B[i]]);
}
}
}
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;
vector<int> ans = base->second;
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;
flip(ans,upd);
iter++;
}
vector<int> heights;
for(int&i:ans)if(i!=-1)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;
}
