#include <bits/stdc++.h>
#define pb push_back
using namespace std;
int sz = 50;
vector<vector<int>> pre;
vector<int> e, vec, cnt;
int a[200001],b[200001];
vector<int> d[200001][2];
void init(int N, int D, int H[]) {
pre.resize(N + 1);
cnt.resize(N + 1, 0);
for (int i = 0; i < N; i++) {
vec.pb(H[i]);
}
}
void curseChanges(int U, int A[], int B[]) {
for (int i = 0; i < U; i++) {
a[i] = A[i];
b[i] = B[i];
}
for (int i = 0; i < U; i++) {
pre[a[i]].pb(i);
pre[b[i]].pb(i);
if ((int)pre[a[i]].size() % sz == 0) {
int h1 = pre[a[i]].size();
int h = h1 - sz;
e.clear();
if (h != 0) {
int h2 = 0;
if (a[pre[a[i]][h - 1]] != a[i]) {
h2 = 1;
}
for (auto x : d[pre[a[i]][h - 1]][h2]) {
e.pb(x);
cnt[x]++;
}
}
for (int j = h; j < h1; j++) {
int h2 = a[pre[a[i]][j]];
if (h2 == a[i]) {
h2 = b[pre[a[i]][j]];
}
cnt[h2]++;
if (cnt[h2] == 1) {
e.pb(h2);
}
}
for (auto x : e) {
if (cnt[x] % 2) {
d[i][0].pb(x);
}
cnt[x] = 0;
}
}
if ((int)pre[b[i]].size() % sz == 0) {
int h1 = pre[b[i]].size();
int h = h1 - sz;
e.clear();
if (h != 0) {
int h2 = 0;
if (a[pre[b[i]][h - 1]] != b[i]) {
h2 = 1;
}
for (auto x : d[pre[b[i]][h - 1]][h2]) {
e.pb(x);
cnt[x]++;
}
}
for (int j = h; j < h1; j++) {
int h2 = b[pre[b[i]][j]];
if (h2 == b[i]) {
h2 = a[pre[b[i]][j]];
}
cnt[h2]++;
if (cnt[h2] == 1) {
e.pb(h2);
}
}
for (auto x : e) {
if (cnt[x] % 2) {
d[i][1].pb(x);
}
cnt[x] = 0;
}
}
}
}
int question(int x, int y, int v) {
vector<int> d1, d2;
if (v == 0) {
return 1e9;
}
v--;
auto it = upper_bound(pre[x].begin(), pre[x].end(), v);
auto it1 = upper_bound(pre[y].begin(), pre[y].end(), v);
if (it == pre[x].begin() || it1 == pre[y].begin()) {
return 1e9;
}
int h = it - pre[x].begin();
int h1 = it1 - pre[y].begin();
int h2, h3;
h2 = h - h % sz;
h3 = h1 - h1 % sz;
e.clear();
if (h2 != 0) {
int tp = 0;
if (a[pre[x][h2 - 1]] != x) {
tp = 1;
}
for (auto z : d[pre[x][h2 - 1]][tp]) {
e.pb(z);
cnt[z]++;
}
}
for (int i = h2; i < h; i++) {
int tp = a[pre[x][i]];
if (tp == x) {
tp = b[pre[x][i]];
}
cnt[tp]++;
if (cnt[tp] == 1) {
e.pb(tp);
}
}
for (auto z : e) {
if (cnt[z] % 2) {
d1.pb(vec[z]);
}
cnt[z] = 0;
}
e.clear();
if (h3 != 0) {
int tp = 0;
if (a[pre[y][h3 - 1]] != y) {
tp = 1;
}
for (auto z : d[pre[y][h3 - 1]][tp]) {
e.pb(z);
cnt[z]++;
}
}
for (int i = h3; i < h1; i++) {
int tp = a[pre[y][i]];
if (tp == y) {
tp = b[pre[y][i]];
}
cnt[tp]++;
if (cnt[tp] == 1) {
e.pb(tp);
}
}
for (auto z : e) {
if (cnt[z] % 2) {
d2.pb(vec[z]);
}
cnt[z] = 0;
}
if(d1.size()==0 || d2.size()==0){
return 1e9;
}
sort(d1.begin(),d1.end());
sort(d2.begin(),d2.end());
int res=1e9;
int j=0;
for(int i=0;i<(int)d1.size();i++){
while(j<(int)d2.size() && d1[i]>d2[j]){
j++;
}
if(j<(int)d2.size()){
res=min(res,d2[j]-d1[i]);
}
}
j=(int)d2.size()-1;
for(int i=(int)d1.size()-1;i>=0;i--){
while(j>=0 && d1[i]<d2[j]){
j--;
}
if(j>=0){
res=min(res,d1[i]-d2[j]);
}
}
return res;
}
