#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> oset;
#define ff first
#define ss second
#define pb push_back
#define all(x) x.begin(), x.end()
#define IMAX INT_MAX
#define IMIN INT_MIN
#define LMAX LLONG_MAX
#define LMIN LLONG_MIN
#define MOD 1000000007
#define SIR 1000000009
int n, d;
vll vals;
struct cmpVals {
bool operator()(const int x, const int y) const {
return (vals[x] < vals[y]);
}
};
struct sused {
int id, zac, kon = IMAX;
sused *prv = nullptr, *nxt = nullptr;
sused(int id, int cas, sused* prv, sused* nxt) : id(id), zac(cas), prv(prv), nxt(nxt) {};
};
struct saman {
map<int, int> sus;
vector<sused*> adj;
sused* last;
saman() {
auto rnd = new sused(-1, -1, nullptr, nullptr);
adj = {rnd};
sus = map<int, int>();
last = adj[0];
}
bool susedi(int id) {
return (sus.find(id) != sus.end());
}
void pridaj(int id, int cas) {
sused* nw = new sused(id, cas, last, nullptr);
sus[id] = adj.size();
adj.pb(nw);
if (last) last->nxt = nw;
last = nw;
}
void odober(int id, int cas) {
int idx = sus[id];
auto torem = adj[idx];
torem->kon = cas;
if (last == torem) last = torem->prv;
auto prv = torem->prv;
auto nxt = torem->nxt;
if (prv) prv->nxt = nxt;
if (nxt) nxt->prv = prv;
sus.erase(id);
}
set<int, cmpVals> najdi_susedov(int cas) {
set<int, cmpVals> res;
int b = 0, e = adj.size();
while (e - b > 1) {
auto ono = adj[(b + e) / 2];
if (ono->zac <= cas)
b = (b + e) / 2;
else
e = (b + e) / 2;
}
auto cur = adj[b];
while (cur->id >= 0) {
if (cur->kon > cas) res.insert(cur->id);
cur = cur->prv;
}
return res;
}
};
vector<saman*> vrch;
void init(int N, int D, int H[]) {
n = N;
d = D;
vals.resize(n);
for (int i = 0; i < n; i++) vals[i] = H[i];
vrch = vector<saman*>(n);
for (int i = 0; i < n; i++) {
vrch[i] = new saman();
}
}
void curseChanges(int U, int A[], int B[]) {
for (int i = 1; i <= U; i++) {
int a = A[i - 1], b = B[i - 1];
if (!vrch[a]->susedi(b)) {
vrch[a]->pridaj(b, i);
vrch[b]->pridaj(a, i);
} else {
vrch[a]->odober(b, i);
vrch[b]->odober(a, i);
}
}
}
int question(int x, int y, int v) {
auto adjx = vrch[x]->najdi_susedov(v);
auto adjy = vrch[y]->najdi_susedov(v);
if (adjx.size() == 0 || adjy.size() == 0) {
return 1000000000;
}
ll best = LMAX;
for (auto a : adjx) {
auto vacsi = adjy.lower_bound(a);
auto mensi = prev(adjy.upper_bound(a));
if (vacsi != adjy.end()) best = min(best, llabs(vals[a] - vals[*vacsi]));
if (mensi != adjy.begin()) best = min(best, llabs(vals[a] - vals[*mensi]));
}
return best;
}
