#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* nxt = nullptr;
vector<pair<int, sused*>> prv = {{0, nullptr}};
sused(int id, int cas) : id(id), zac(cas) {
prv = {{0, nullptr}};
nxt = nullptr;
};
};
struct saman {
map<int, int> sus;
vector<sused*> adj;
sused* last;
saman() {
auto rnd = new sused(-1, -1);
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);
nw->prv.emplace_back(cas, last);
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.back().ss;
auto prvs = torem->prv.back().ss;
auto nxts = torem->nxt;
if (prvs) prvs->nxt = nxts;
if (nxts) nxts->prv.emplace_back(cas, prvs);
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);
b = 0; e = cur->prv.size();
while (e - b > 1) {
int tmp = cur->prv[(b+e)/2].ff;
if (tmp > cas) e = (b+e)/2;
else b = (b+e)/2;
}
cur = cur->prv[b].ss;
}
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 = adjy.upper_bound(a);
if (vacsi != adjy.end()) best = min(best, llabs(vals[a] - vals[*vacsi]));
if (prev(mensi) != adjy.begin()) best = min(best, llabs(vals[a] - vals[*prev(mensi)]));
}
return best;
}
// int main() {
// int N, D, U, Q;
// std::ios::sync_with_stdio(false); std::cin.tie(NULL);
// std::cin >> N >> D >> U >> Q;
// int *F = new int[N];
// for (int i=0; i<N; i++)
// std::cin >> F[i];
// init(N, D, F);
// int *A = new int[U], *B = new int[U];
// for (int i=0; i<U; i++) {
// std::cin >> A[i] >> B[i];
// }
// curseChanges(U, A, B);
// bool correct = true;
// for (int i=0; i<Q; i++) {
// int X,Y,V,CorrectAnswer;
// std::cin >> X >> Y >> V >> CorrectAnswer;
// int YourAnswer = question(X,Y,V);
// if (YourAnswer != CorrectAnswer) {
// std::cout << "WA! Question: " << i
// << " (X=" << X << ", Y=" << Y << ", V=" << V << ") "
// << "Your answer: " << YourAnswer
// << " Correct Answer: " << CorrectAnswer << std::endl;
// correct = false;
// } else {
// std::cerr << YourAnswer << " - OK" << std::endl;
// }
// }
// if (correct) {
// std::cout << "Correct." << std::endl;
// } else std::cout << "Incorrect." << std::endl;
// return 0;
// }
