// ~Be name khoda~ //
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
#define mp make_pair
#define all(x) x.begin(), x.end()
#define fi first
#define se second
#define cl clear
#define endll '\n'
const int maxn = 1e6 + 10;
const int maxn5 = 1e5 + 10;
const int maxnt = 1.2e6 + 10;
const int maxn3 = 1e3 + 10;
const int mod = 1e9 + 7;
const int ssq = 503;
const ll inf = 2e18;
int n, d, u, h[maxn5], val[2 * maxn5];
vector <int> ver1, ver2, adj[maxn5], lim[maxn5];
map <int, int> have[maxn5];
pair <int, int> e[2 * maxn5];
inline bool cmp (int a, int b){
return val[a] < val[b];
}
void init(int N, int D, int H[]) {
n = N;
d = D;
for(int i = 0; i < n; i++) h[i] = H[i];
return;
}
void curseChanges(int U, int A[], int B[]) {
u = U;
for(int i = 0; i < u; i++){
int a = A[i];
int b = B[i];
e[i] = {a, b};
if(have[b].find(a) == have[b].end()){
adj[b].pb(i);
have[b][a] = i;
}
else{
val[have[b][a]] = i;
have[b].erase(a);
}
if(have[a].find(b) == have[a].end()){
adj[a].pb(i);
have[a][b] = i;
}
else{
val[have[a][b]] = i;
have[a].erase(b);
}
}
for(int i = 0; i < n; i++) for(auto it = have[i].begin(); it != have[i].end(); it++) val[it->se] = u + 10;
for(int i = 0; i < n; i++){
int ind = 0;
while(ind < adj[i].size()){
lim[i].pb(adj[i][min(ind + ssq - 1, int(adj[i].size()) - 1)]);
sort(adj[i].begin() + ind, adj[i].begin() + min(ssq + ind, int(adj[i].size())), cmp);
ind += ssq;
}
}
return;
}
int question(int x, int y, int v) {
if(v == 0) return 1000000000;
ver1.clear(); ver2.clear();
v--;
int ind = 0, num = 0;
while(ind < adj[x].size()){
if(lim[x][num] <= v){
int j = min(ind + ssq - 1, int(adj[x].size()) - 1);
while(j >= ind && val[adj[x][j]] > v){
int u = e[adj[x][j]].fi;
if(u == x) u = e[adj[x][j]].se;
ver1.pb(h[u]);
j--;
}
}
else{
int j = ind;
for(; j < min(ind + ssq, int(adj[x].size())); j++){
if(adj[x][j] <= v && val[adj[x][j]] > v){
int u = e[adj[x][j]].fi;
if(u == x) u = e[adj[x][j]].se;
ver1.pb(h[u]);
}
}
}
num++;
ind += ssq;
}
ind = 0, num = 0; x = y;
while(ind < adj[x].size()){
if(lim[x][num] <= v){
int j = min(ind + ssq - 1, int(adj[x].size()) - 1);
while(j >= ind && val[adj[x][j]] > v){
int u = e[adj[x][j]].fi;
if(u == x) u = e[adj[x][j]].se;
ver2.pb(h[u]);
j--;
}
}
else{
int j = ind;
for(; j < min(ind + ssq, int(adj[x].size())); j++){
if(adj[x][j] <= v && val[adj[x][j]] > v){
int u = e[adj[x][j]].fi;
if(u == x) u = e[adj[x][j]].se;
ver2.pb(h[u]);
}
}
}
num++;
ind += ssq;
}
if(ver1.empty() || ver2.empty()) return 1000000000;
sort(all(ver1));
sort(all(ver2));
ind = 0;
int ans = 1000000000;
for(int i = 0; i < ver1.size(); i++){
while(ind < ver2.size() && ver2[ind] <= ver1[i]) ind++;
if(ind > 0) ans = min(ans, ver1[i] - ver2[ind - 1]);
if(ind < ver2.size()) ans = min(ans, ver2[ind] - ver1[i]);
}
return ans;
}
