/* https://codeforces.com/blog/entry/82022 */
#include <stdlib.h>
#include <string.h>
#define N 100000
#define M 200000
#define D 500
#define B 50 /* B = floor(sqrt(M)) */
#define K (M / B)
#define INF 1000000000
int abs_(int a) { return a > 0 ? a : -a; }
int min(int a, int b) { return a < b ? a : b; }
int aa[N], n, d;
void init(int n_, int d_, int *aa_) {
memcpy(aa, aa_, (n = n_) * sizeof *aa_), d = d_;
}
int *jj[N], kk[N], *eh[N], *ep[N], *eq[N], **ejj[N], eo[N];
void append(int i, int h, int p, int q) {
int o = eo[i]++;
eh[i][o] = h, ep[i][o] = p, eq[i][o] = q;
if ((o + 1) % B == 0)
memcpy(ejj[i][o / B], jj[i], kk[i] * sizeof *jj[i]);
}
void update(int i, int j, int h) {
int g;
for (g = 0; g < kk[i]; g++)
if (jj[i][g] == j) {
int p;
p = g == 0 ? n : jj[i][g - 1];
kk[i]--;
for ( ; g < kk[i]; g++)
jj[i][g] = jj[i][g + 1];
append(i, h, p, j);
return;
}
kk[i]++;
for (g = kk[i] - 1; g > 0 && aa[jj[i][g - 1]] > aa[j]; g--)
jj[i][g] = jj[i][g - 1];
jj[i][g] = j;
append(i, h, g == 0 ? n : jj[i][g - 1], j);
}
void curseChanges(int m, int *uu, int *vv) {
int g, h, i, j;
for (h = 0; h < m; h++) {
i = uu[h], j = vv[h];
eo[i]++, eo[j]++;
}
for (i = 0; i < n; i++) {
int k;
jj[i] = (int *) malloc(eo[i] * sizeof *jj[i]);
eh[i] = (int *) malloc(eo[i] * sizeof *eh[i]);
ep[i] = (int *) malloc(eo[i] * sizeof *ep[i]);
eq[i] = (int *) malloc(eo[i] * sizeof *eq[i]);
ejj[i] = (int **) malloc((k = eo[i] / B) * sizeof *ejj[i]);
for (g = 0; g < k; g++) {
ejj[i][g] = (int *) malloc(d * sizeof *ejj[i][g]);
memset(ejj[i][g], -1, d * sizeof *ejj[i][g]);
}
eo[i] = 0;
}
for (h = 0; h < m; h++) {
i = uu[h], j = vv[h];
update(i, j, h), update(j, i, h);
}
}
int next[N + 1];
int query_(int *aa_, int i, int o) {
int g = (o + 1) / B - 1, h, j, o_, cnt;
if (g == -1)
next[n] = -1;
else {
for (h = 0; h < d && ejj[i][g][h] != -1; h++)
next[h == 0 ? n : ejj[i][g][h - 1]] = ejj[i][g][h];
next[h == 0 ? n : ejj[i][g][h - 1]] = -1;
}
for (o_ = (g + 1) * B; o_ <= o; o_++) {
int p = ep[i][o_], q = eq[i][o_];
if (next[p] != q)
next[q] = next[p], next[p] = q;
else
next[p] = next[q];
}
cnt = 0;
for (j = next[n]; j != -1; j = next[j])
aa_[cnt++] = aa[j];
return cnt;
}
int query(int *aa, int i, int h) {
int lower = -1, upper = eo[i];
while (upper - lower > 1) {
int o = (lower + upper) / 2;
if (eh[i][o] < h)
lower = o;
else
upper = o;
}
return query_(aa, i, lower);
}
int question(int i, int j, int h_) {
static int aa[D], bb[D];
int n, m, ans;
n = query(aa, i, h_), m = query(bb, j, h_);
i = 0, j = 0, ans = INF;
while (i < n && j < m) {
ans = min(ans, abs_(aa[i] - bb[j]));
if (aa[i] < bb[j])
i++;
else
j++;
}
return ans;
}
