#include <bits/stdc++.h>
using namespace std;
const int N = 100000, B = 300;
int n, d, u, q, h[N];
vector<vector<tuple<int, int, int>>> ev[N];
vector<int> tt[N];
void init(int n_, int d_, int h_[]) {
n = n_, d = d_;
for (int i = 0; i < n; i++)
h[i] = h_[i];
}
void curseChanges(int u_, int i_[], int j_[]) {
u = u_;
for (int k = 1; k <= u; k++) {
int i = i_[k - 1], j = j_[k - 1];
if (ev[i].size() == 0 || (int) ev[i].back().size() == B) {
if (ev[i].size() == 0)
ev[i].push_back({});
else {
sort(ev[i].back().begin(), ev[i].back().end());
vector<pair<int, int>> v;
for (auto [w, x, t] : ev[i].back())
if (v.size() == 0 || v.back() != make_pair(w, x))
v.push_back({w, x});
else
v.pop_back();
ev[i].push_back({});
for (auto [w, x] : v)
ev[i].back().push_back(make_tuple(w, x, k - 1));
}
tt[i].push_back(k);
}
ev[i].back().push_back({h[j], j, k});
if (ev[j].size() == 0 || (int) ev[j].back().size() == B) {
if (ev[j].size() == 0)
ev[j].push_back({});
else {
sort(ev[j].back().begin(), ev[j].back().end());
vector<pair<int, int>> v;
for (auto [w, x, t] : ev[j].back())
if (v.size() == 0 || v.back() != make_pair(w, x))
v.push_back({w, x});
else
v.pop_back();
ev[j].push_back({});
for (auto [w, x] : v)
ev[j].back().push_back(make_tuple(w, x, k - 1));
}
tt[j].push_back(k);
}
ev[j].back().push_back({h[i], i, k});
}
for (int i = 0; i < n; i++)
if (ev[i].size())
sort(ev[i].back().begin(), ev[i].back().end());
}
int question(int i, int j, int k) {
int p;
if (tt[i].size() == 0 || tt[j].size() == 0 || tt[i][0] > k || tt[j][0] > k)
return 1000000000;
p = upper_bound(tt[i].begin(), tt[i].end(), k) - tt[i].begin() - 1;
vector<pair<int, int>> wi;
for (auto [w, x, t] : ev[i][p]) {
if (t > k)
continue;
if (wi.size() == 0 || wi.back() != make_pair(w, x))
wi.push_back({w, x});
else
wi.pop_back();
}
p = upper_bound(tt[j].begin(), tt[j].end(), k) - tt[j].begin() - 1;
vector<pair<int, int>> wj;
for (auto [w, x, t] : ev[j][p]) {
if (t > k)
continue;
if (wj.size() == 0 || wj.back() != make_pair(w, x))
wj.push_back({w, x});
else
wj.pop_back();
}
int ans = 1000000000;
for (int l = 0, r = 0; l < (int) wi.size(); l++) {
while (r < (int) wj.size() && wi[l].first > wj[r].first)
ans = min(ans, wi[l].first - wj[r++].first);
if (r < (int) wj.size())
ans = min(ans, wj[r].first - wi[l].first);
}
return ans;
}
