#include <bits/stdc++.h>
#ifndef EVAL
#include "grader.cpp"
#endif
using namespace std;
/*
6 5 11 4
2 42 1000 54 68 234
0 1
2 0
3 4
3 5
3 5
1 3
5 3
0 5
3 0
1 3
3 5
0 3 4 26
3 0 8 0
0 5 5 1000000000
3 0 11 14
*/
namespace sOlUTiON {
using u32 = unsigned int;
// 282
using bit = array<u32, 283>;
constexpr int N = 1E5, M = 2E5;
int n, D;
int h[N];
vector<int> f[N], add[N];
vector<bit> a[N];
bit compress(vector<int> &a) {
int j = 0, k = 0;
bit res{};
for (int i = 0; i < int(a.size()); i++) {
if (j + 18 <= 32) {
res[k] |= a[i] << j;
j += 18;
if (j == 32) {
j = 0;
k++;
}
} else {
res[k] |= a[i] << j;
int x = 32 - j;
j += 18;
j -= 32;
k++;
res[k] |= a[i] >> x;
}
}
res[282] = a.size();
return res;
}
vector<int> decompress(bit a) {
int n = a[282];
int j = 0, k = 0;
vector<int> ans(n);
for (int i = 0; i < n; i++) {
if (j + 18 <= 32) {
ans[i] = a[k] >> j;
j += 18;
if (j == 32) {
j = 0;
k++;
}
} else {
ans[i] |= a[k] >> j;
int x = 32 - j;
j += 18;
j -= 32;
k++;
ans[i] |= a[k] << x;
}
}
for (int &x : ans) x &= (1 << 18) - 1;
return ans;
}
};
using namespace sOlUTiON;
void init(int _N, int _D, int H[]) {
n = _N;
D = _D;
for (int i = 0; i < n; i++) {
h[i] = H[i];
}
}
void Add(vector<int> &b, int v) {
vector<int> w;
int j = 0;
while (j < int(b.size()) && (b[j] != v && h[b[j]] <= h[v]))
w.push_back(b[j++]);
if (j < int(b.size()) && b[j] == v) {
j++;
} else {
w.push_back(v);
}
while (j < int(b.size()))
w.push_back(b[j++]);
b = w;
}
void curseChanges(int U, int A[], int B[]) {
int cnt[n] {};
for (int i = 0; i < U; i++) {
cnt[A[i]]++;
cnt[B[i]]++;
}
for (int i = 0; i < n; i++) {
a[i].reserve(cnt[i] / 2);
}
for (int i = 0; i < U; i++) {
int u = A[i];
int v = B[i];
{
vector<int> b, w;
if (add[u].size() % 2 == 0) {
add[u].push_back(v);
} else {
if (!a[u].empty()) {
b = decompress(a[u].back());
}
Add(b, add[u].back());
int j = 0;
while (j < int(b.size()) && (b[j] != v && h[b[j]] <= h[v]))
w.push_back(b[j++]);
if (j < int(b.size()) && b[j] == v) {
j++;
} else {
w.push_back(v);
}
while (j < int(b.size()))
w.push_back(b[j++]);
a[u].push_back(compress(w));
add[u].push_back(v);
}
}
{
vector<int> b, w;
if (add[v].size() % 2 == 0) {
add[v].push_back(u);
} else {
if (!a[v].empty()) {
b = decompress(a[v].back());
}
Add(b, add[v].back());
int j = 0;
while (j < int(b.size()) && (b[j] != u && h[b[j]] <= h[u]))
w.push_back(b[j++]);
if (j < int(b.size()) && b[j] == u) {
j++;
} else {
w.push_back(u);
}
while (j < int(b.size()))
w.push_back(b[j++]);
a[v].push_back(compress(w));
add[v].push_back(u);
}
}
f[u].push_back(i + 1);
f[v].push_back(i + 1);
}
for (int i = 0; i < n; i++) {
assert(a[i].size() == a[i].capacity());
}
}
int question(int x, int y, int v) {
int p1 = upper_bound(f[x].begin(), f[x].end(), v) - f[x].begin() - 1;
int p2 = upper_bound(f[y].begin(), f[y].end(), v) - f[y].begin() - 1;
int ans = 1E9;
if (p1 == -1 || p2 == -1) {
return ans;
}
vector<int> f, s;
if (p1 % 2 == 0) {
if (p1 > 0) {
f = decompress(a[x][(p1 - 1) / 2]);
}
Add(f, add[x][p1]);
} else {
f = decompress(a[x][p1 / 2]);
}
if (p2 % 2 == 0) {
if (p2 > 0) {
s = decompress(a[y][(p2 - 1) / 2]);
}
Add(s, add[y][p2]);
} else {
s = decompress(a[y][p2 / 2]);
}
int s1 = f.size();
int s2 = s.size();
if (s1 == 0 || s2 == 0)
return ans;
int j = 0;
for (int i = 0; i < s1; i++) {
int t = h[f[i]];
while (j + 1 < s2 && h[s[j]] < t)
j++;
ans = min(ans, abs(h[f[i]] - h[s[j]]));
}
j = 0;
for (int i = 0; i < s2; i++) {
int t = h[s[i]];
while (j + 1 < s1 && h[f[j]] < t)
j++;
ans = min(ans, abs(h[s[i]] - h[f[j]]));
}
return ans;
}
