#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template<class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<class T> using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define ll long long
#define int long long
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define F first
#define S second
#define rep(i,a,b) for (int i = (a); i < (b); ++i)
#define per(i,a,b) for (int i = (a); i >= (b); --i)
#define each(x, a) for (auto &x : a)
#define INF 1e18
#define MOD 1000000007
#define MOD2 998244353
#define pyset unordered_set
#define vec vector
#define pii pair<int,int>
#define vi vector<int>
#define vpii vector<pair<int,int>>
#define gpmap gp_hash_table
#define gpmapii gp_hash_table<int,int>
int n,u,k;
vec<vec<pair<int,set<pii>>>> adj;
vi c;
vi h;
void init(int N, int D, int H[]){
n=N;
int k = D/9;
adj.assign(n,{{0,{}}});
c.assign(n,0);
rep(i,0,n) h[i] = H[i];
}
void curseChanges(int U, int A[], int B[]){
u = U;
rep(i,0,u){
int a = A[i];
int b = B[i];
c[a]++;c[b]++;
rep(j,0,2){
adj[a].pb({i+1,{{h[b],b}}});
if(c[a]%k == 0){
set<pii> &cur = adj[a][c[a]].S;
cur = adj[a][c[a]-k].S;
if(cur.find({h[b],b}) == cur.end()){
cur.insert({h[b],b});
}
else{
cur.erase({h[b],b});
}
per(j,c[a]-1,c[a]-k+1){
each(x,adj[a][j].S){
if(cur.find(x) == cur.end()){
cur.insert(x);
}
else{
cur.erase(x);
}
}
}
}
swap(a,b);
}
}
}
int question(int X, int Y, int V){
set<pii> curx;
set<pii> cury;
X;Y;
rep(j,0,2){
int l = 0;
int r = c[X]+1;
while(r-l>1){
int m = (r+l)/2;
if(adj[X][m].F > V){
r=m;
}
else{
l=m;
}
}
int start = l - l%k;
cury = adj[X][start].S;
rep(i,start+1,l+1){
pii x = *adj[X][i].S.begin();
if(cury.find(x) == cury.end()){
cury.insert(x);
}
else{
cury.erase(x);
}
}
swap(X,Y);
swap(curx,cury);
}
int res = 1e9;
if(curx.empty() || cury.empty()) return res;
auto ity = cury.begin();
auto nity = cury.begin();
nity++;
each(x,curx){
while(nity != cury.end() && (*nity).F < x.F){
nity++;
ity++;
}
if(nity != cury.end()) res = min(res,min(abs(x.F-(*ity).F),(*nity).F-x.F));
else res = min(res,abs(x.F-(*ity).F));
}
return res;
}
// signed main(){
// ios::sync_with_stdio(0);
// cin.tie(0);
// int N,U,Q;
// cin >> N >> U >> Q;
// vi H(N);
// each(x,H) cin >> x;
// init(N,U,Q,H);
// vi A(U);
// vi B(U);
// each(x,A) cin >> x;
// each(x,B) cin >> x;
// CurseChanges(A,B);
// rep(i,0,q){
// int X,Y,D;
// cin >> X >> Y >> D;
// cout << solve(X,Y,D) << endl;
// }
// return 0;
// }
