#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define ff first
#define ss second
using namespace std;
const int INF = 1000000000;
int N, D, U, BLOCK;
vector<int> H, cnt_changes;
vector<vector<pair<int, multiset<pii>>>> states;
vector<multiset<pii>> cur_states;
vector<pii> changes;
vector<vector<int>> node_changes;
void init(int n, int d, int h[])
{
N = n;
D = d;
H.resize(N);
states.resize(N);
cur_states.resize(N, {});
node_changes.resize(N, {});
for (int i = 0; i < N; i++)
H[i] = h[i];
for (int i = 0; i < N; i++)
states[i].push_back({0, {}});
}
void curseChanges(int u, int A[], int B[])
{
U = u;
BLOCK = sqrtl(U);
cnt_changes.resize(N, 0);
changes.resize(U + 1);
for (int i = 1; i <= U; i++)
{
changes[i] = {A[i - 1], B[i - 1]};
node_changes[A[i - 1]].push_back(i);
node_changes[B[i - 1]].push_back(i);
}
for (int v = 1; v <= U; v++)
{
int a = A[v - 1], b = B[v - 1];
if (cnt_changes[a] >= BLOCK)
{
states[a].push_back({v, {}});
for (auto x : cur_states[a])
states[a].back().ss.insert(x);
cnt_changes[a] = 0;
}
if (cnt_changes[b] >= BLOCK)
{
states[b].push_back({v, {}});
for (auto x : cur_states[b])
states[b].back().ss.insert(x);
cnt_changes[b] = 0;
}
cnt_changes[a]++;
cnt_changes[b]++;
if (cur_states[a].count({H[b], b}))
cur_states[a].erase(cur_states[a].find({H[b], b}));
else
cur_states[a].insert({H[b], b});
if (cur_states[b].count({H[a], a}))
cur_states[b].erase(cur_states[b].find({H[a], a}));
else
cur_states[b].insert({H[a], a});
}
}
multiset<pii> get_set(int x, int v)
{
int l = 0, r = states[x].size() - 1;
int lb = 0;
while (l <= r)
{
int m = l + (r - l) / 2;
if (states[x][m].ff <= v)
{
lb = m;
l = m + 1;
}
else
r = m - 1;
}
int cur_v = states[x][lb].ff;
multiset<pii> cur = states[x][lb].ss;
auto iter = lower_bound(node_changes[x].begin(), node_changes[x].end(), cur_v);
while (iter != node_changes[x].end() && *iter <= v)
{
int idx = *iter;
auto [a, b] = changes[idx];
if (a != x)
swap(a, b);
if (cur.count({H[b], b}))
cur.erase(cur.find({H[b], b}));
else
cur.insert({H[b], b});
cur_v = idx;
iter++;
}
return cur;
}
int question(int x, int y, int v)
{
multiset<pii> a = get_set(x, v), b = get_set(y, v);
if (a.empty() || b.empty())
return INF;
int ret = INF;
for (auto [hei, _] : a)
{
auto lwr = b.lower_bound({hei, -1});
if (lwr != b.end())
ret = min(ret, abs(lwr->first - hei));
if (lwr != b.begin())
{
--lwr;
ret = min(ret, abs(hei - lwr->first));
}
}
return ret;
}
// 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;
// }
