#include<map>
#include<algorithm>
#include<cstdio>
#include<cassert>
#include<vector>
#include<utility>
#define printf(...) 42
#define puts(...) 42
struct LCT{
struct node{
int pa,c[2],rev;
long long val,sum;
node(){
pa=c[0]=c[1]=rev=0;val=sum=0;
}
};
std::vector<node>t;
void sz(int n){ t.assign(n,node());}
int nrt(int v){return t[t[v].pa].c[0]==v||t[t[v].pa].c[1]==v;}
void tagrev(int v){ if(!v)return; t[v].rev^=1; std::swap(t[v].c[0],t[v].c[1]); }
void pushdown(int v){ if(t[v].rev){ tagrev(t[v].c[0]);tagrev(t[v].c[1]); t[v].rev=0; } }
void pushup(int v){ pushdown(t[v].c[0]);pushdown(t[v].c[1]);t[v].sum=t[v].val+t[t[v].c[0]].sum+t[t[v].c[1]].sum; }
void rot(int v){
int p=t[v].pa,g=t[p].pa,d=t[p].c[1]==v;
if(nrt(p))t[g].c[t[g].c[1]==p]=v;
pushdown(v);
t[p].c[d]=t[v].c[!d];
if(t[v].c[!d])t[t[v].c[!d]].pa=p;
t[v].c[!d]=p;
t[t[p].pa=v].pa=g;
pushup(p);pushup(v);
}
void upd(int v){if(nrt(v))upd(t[v].pa);pushdown(v);}
void splay(int v){
upd(v);
for(int p;nrt(v);rot(v)) if(nrt(p=t[v].pa))rot((t[t[p].pa].c[1]==p)==(t[p].c[1]==v)?p:v);
pushup(v);
}
void access(int v){ for(int w=0;v;v=t[w=v].pa)splay(v),t[v].c[1]=w,pushup(v); }
void evert(int v){ access(v);splay(v);tagrev(v);}
void split(int v,int w){evert(v);access(w);splay(w);}
void link(int v,int w){
evert(v);access(w);splay(w);t[v].pa=w;}
void cut(int v){ access(v);splay(v); t[t[v].c[0]].pa=0; t[v].c[0]=0;pushup(v);}
}lc;
std::vector<std::pair<int,int>>nei;
int ii,jj,iii,skibidize[2222222];
std::map<int,int>sh,rsh,weigh[1000000];
void init()
{
ii=iii=1;
lc.sz(2000000);
jj=1000000;
sh[1]=1;
}
void link_weight(int v,int w,int dist){
int x;
x=weigh[v][w]=weigh[w][v]=++jj;
lc.t[x].val=dist;lc.pushup(x);
lc.link(x,v);
lc.link(x,w);
skibidize[x]=std::max(rsh[v],rsh[w])-dist+1;
}
void ensure_point(int i){
if(sh.count(i))return;
auto it=std::lower_bound(nei.begin(),nei.end(),std::make_pair(i+1,-1));
assert(it!=nei.begin());
int ll=prev(it)->second,rr=it->second;
rsh[sh[i]=++ii]=i;
int x=weigh[sh[ll]][sh[rr]];
printf(" Killing %d between %d %d\n",x,sh[ll],sh[rr]);
lc.evert(x);
lc.cut(sh[ll]);
lc.cut(sh[rr]);
link_weight(sh[ll],ii,i-prev(it)->first+1);
link_weight(sh[rr],ii,it->first-i);
}
void path(int a, int s)
{
ensure_point(a);
nei.emplace_back(iii+1,a);
iii+=s;
rsh[sh[iii]=++ii]=iii;
int b=iii;
nei.emplace_back(iii,b);
link_weight(sh[a],sh[b],s);
}
int take=0;
int findright(int v,int k){
lc.pushdown(v);
lc.pushup(v);
int rightsum=lc.t[lc.t[v].c[1]].sum,cursum=rightsum+take+lc.t[v].val;
printf(" -- %d %d %d -- %d %d %d\n",v,lc.t[v].c[0],lc.t[v].c[1],take,rightsum,lc.t[v].val);
if(take+rightsum>=k){
return findright(lc.t[v].c[1],k);
}else if(cursum>=k){
printf(" Got at %d = %d\n",v,cursum);
take=cursum;
return v;
}else{
take=cursum;
return findright(lc.t[v].c[0],k);
}
}
int dig(int a, int b)
{
ensure_point(a);
ensure_point(b);
a=sh[a],b=sh[b];
lc.split(a,b);
printf(" Try %d to %d\n",a,b);
int ans;
int lef=(lc.t[b].sum+1)/2;
take=0;
printf(" Want %d\n",lef);
int v=findright(b,lef);
printf(" Take=%d\n",take);
lef=lc.t[b].sum/2-(lc.t[b].sum-take);
printf(" Lef=%d\n",lef);
if(lc.t[v].val==0){
//printf("%d\n",rsh[v]);
puts("A");
ans=rsh[v];
}else if(lc.t[v].val==1){
//printf("%d\n",skibidize[v]);
puts("B");
ans=skibidize[v];
}else{
puts("C");
ans=skibidize[v]-1+lef;
// printf("%d\n",v);
}
lc.access(v);
return ans;
}
#undef puts
#undef printf
