#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define len(s) (int)(s.size())
#define F first
#define S second
#define pll pair < int , int >
const int N = 2e5;
int n , d , h[N];
int u , a[N], b[N];
pll last[N];
vector < int > g[N][2];
vector < int > f[N];
map < pll , int > mp;
void init(int N, int D, int H[]) {
n = N;
d = D;
for(int i = 0; i < n; i++) h[i] = H[i];
}
void curseChanges(int U, int A[], int B[]) {
u = U;
for(int i = 0; i < u; i++){
a[i] = A[i];
b[i] = B[i];
if(!last[a[i]].F) g[i][0].pb(b[i]);
else{
for(int it : g[last[a[i]].F][last[a[i]].S]) g[i][0].pb(it);
if(!mp[{a[i] , b[i]}]) g[i][0].pb(b[i]);
else{
vector < int > zam;
for(int it : g[i][0]){
if(it != b[i]) zam.pb(it);
}
g[i][0].clear();
for(int it : zam) g[i][0].pb(it);
}
}
if(!last[b[i]].F) g[i][1].pb(a[i]);
else{
for(int it : g[last[b[i]].F][last[b[i]].S]) g[i][1].pb(it);
if(!mp[{a[i] , b[i]}]) g[i][1].pb(a[i]);
else{
vector < int > zam;
for(int it : g[i][1]){
if(it != a[i]) zam.pb(it);
}
g[i][1].clear();
for(int it : zam) g[i][1].pb(it);
}
}
last[a[i]] = {i , 0};
last[b[i]] = {i , 1};
mp[{a[i] , b[i]}] ^= 1;
mp[{b[i] , a[i]}] ^= 1;
f[a[i]].pb(i);
f[b[i]].pb(i);
}
}
int find(int x , int w){
int l = 0 , r = len(f[x]) - 1 , res = u;
while(l <= r){
int mid = (l + r) >> 1;
if(f[x][mid] <= w){
l = mid + 1;
res = mid;
}
else{
r = mid - 1;
}
}
return res;
}
int question(int x, int y, int v) {
int lstx = find(x , v) , lsty = find(y , v);
if(lstx == u || lsty == u) return 1000000000;
int mn = 1000000000;
int c = 0 , d = 0;
if(a[f[x][lstx]] != x) c++;
if(a[f[y][lsty]] != y) d++;
for(int it : g[f[x][lstx]][c]){
for(int it2 : g[f[y][lsty]][d]){
mn = min(mn , abs(h[it] - h[it2]));
}
}
return mn;
}
// int main(){
//
// }
