#include <bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;
const int INF = 1e9, N = 2e5;
int n, u, d, s4=1;
int h[N], a[N], b[N], ans0[N], ans1[N], last0[N], last1[N];
set<int> g[N], e[N];
vector< pair<int, int> > iv0[N], iv1[N];
void init(int N, int D, int H[]){
n = N, d = D;
for(int i = 0; i < n; i++) h[i] = H[i];
for(int i = 0; i < n; i++) if(h[i] > 1) s4 = 0;
}
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(!s4) return;
for(int i = 0; i < u; i++){
if(e[a[i]].count(b[i])){
e[a[i]].erase(b[i]), e[b[i]].erase(a[i]);
if(h[b[i]]){
if(!--ans1[a[i]])
iv1[a[i]].push_back({last1[a[i]], i});
}
else{
if(!--ans0[a[i]])
iv0[a[i]].push_back({last0[a[i]], i});
}
if(h[a[i]]){
if(!--ans1[b[i]])
iv1[b[i]].push_back({last1[b[i]], i});
}
else{
if(!--ans0[b[i]])
iv0[b[i]].push_back({last0[b[i]], i});
}
}
else{
e[a[i]].insert(b[i]), e[b[i]].insert(a[i]);
if(h[b[i]]){
if(!ans1[a[i]]++) last1[a[i]] = i+1;
}
else{
if(!ans0[a[i]]++) last0[a[i]] = i+1;
}
if(h[a[i]]){
if(!ans1[b[i]]++) last1[b[i]] = i+1;
}
else{
if(!ans0[b[i]]++) last0[b[i]] = i+1;
}
}
}
for(int i = 0; i < n; i++){
if(ans0[i]) iv0[i].push_back({last0[i], u});
if(ans1[i]) iv1[i].push_back({last1[i], u});
}
}
int dis(int a, int b){
return max(h[a], h[b]) - min(h[a], h[b]);
}
int st2(int X, int Y, int V){
int sol = INF;
vector<int> cng;
for(int i = 0; i < V; i++){
if(g[a[i]].count(b[i])) g[a[i]].erase(b[i]),
g[b[i]].erase(a[i]);
else g[a[i]].insert(b[i]), g[b[i]].insert(a[i]);
cng.push_back(a[i]), cng.push_back(b[i]);
}
for(int x : g[X]) for(int y : g[Y]) sol = min(sol, dis(x, y));
while(!cng.empty()) g[cng.back()].clear(), cng.pop_back();
return sol;
}
int st4(int X, int Y, int V){
int x0 = 0, x1 = 0, y0 = 0, y1 = 0;
pair<int, int> temp = {V,INF};
auto it0x = upper_bound(iv0[X].begin(), iv0[X].end(), temp);
if(it0x != iv0[X].begin()){
it0x--;
if(it0x->second >= V) x0 = 1;
}
auto it1x = upper_bound(iv1[X].begin(), iv1[X].end(), temp);
if(it1x != iv1[X].begin()){
it1x--;
if(it1x->second >= V) x1 = 1;
}
auto it0y = upper_bound(iv0[Y].begin(), iv0[Y].end(), temp);
if(it0y != iv0[Y].begin()){
it0y--;
if(it0y->second >= V) y0 = 1;
}
auto it1y = upper_bound(iv1[Y].begin(), iv1[Y].end(), temp);
if(it1y != iv1[Y].begin()){
it1y--;
if(it1y->second >= V) y1 = 1;
}
if((x0 && y0) || (x1 && y1)) return 0;
if((x0 || x1) && (y0 || y1)) return 1;
return INF;
}
int question(int X, int Y, int V){
if(s4) return st4(X, Y, V);
return st2(X, Y, V);
}
