#include"long.h"
#include<bits/stdc++.h>
using namespace std;
namespace zx2003{
// https://zx2003.blog.uoj.ac/blog/7884
// https://paste.ubuntu.com/p/yT5ZJRgNzf/
typedef unsigned ui;
inline void upa(ui&a,ui b){a<b?a=b:0;}
mt19937 R(114514);
const int N=1e5+5,B=150;
int n,q,i,j,dad[N];
infoset val[N];ui prio[N];
struct node{
int ch[2],fa,sz,qsz,sz2;
ui p;
infoset ss,ts;
}t[N];
inline bool nrt(int x){return t[t[x].fa].ch[0]==x || t[t[x].fa].ch[1]==x;}
inline void upd(int x){
t[x].sz=t[t[x].ch[0]].sz+t[t[x].ch[1]].sz+1;
t[x].sz2=t[t[x].ch[0]].sz2+t[t[x].ch[1]].sz2+t[x].qsz+1;
if(t[x].sz2<=B){
int o=t[t[x].ch[1]].ss.size()<t[t[x].ch[0]].ss.size();
t[x].ts=merge(t[t[x].ch[o]].ss,val[x]);
t[x].ss=merge(t[t[x].ch[!o]].ss,t[x].ts);
}
}
inline int dir(int x,int y){return t[x].ch[1]==y;}
inline void rotate(int x){
int y=t[x].fa,z=t[y].fa,o=dir(y,x);
if(nrt(y))t[z].ch[dir(z,y)]=x;t[x].fa=z;
t[y].ch[o]=t[x].ch[!o];t[t[x].ch[!o]].fa=y;
t[x].ch[!o]=y;t[y].fa=x;upd(y);
}
inline void uprot(int x){for(;nrt(x) && t[x].p>t[t[x].fa].p;rotate(x));}
inline void downrot(int x){
int a,b;
for(;;)if(max(t[a=t[x].ch[0]].p,t[b=t[x].ch[1]].p)>t[x].p)
rotate(t[a].p>t[b].p?a:b);else break;
}
set<pair<ui,int>>se[N];
inline int getrt(int x){for(;nrt(x);x=t[x].fa);return x;}
inline int go(int x,int o){for(;t[x].ch[o];x=t[x].ch[o]);return x;}
inline int getdep(int x){int d=0;for(;x;x=t[x].fa)++d;return d;}
inline int getrk(int x){
int rk=t[t[x].ch[0]].sz+1,y;
for(;nrt(x);)y=t[x].fa,rk+=t[y].ch[1]==x?t[t[y].ch[0]].sz+1:0,x=y;
return rk;
}
inline ui getmx(int x){
ui ret=t[t[x].ch[1]].p;int y;
for(;nrt(x);)y=t[x].fa,upa(ret,x==t[y].ch[0]?t[y].p:0),x=y;
return ret;
}
void split(int x,int&L,int&R,int tp){
if(tp==0)L=x,R=t[x].ch[1],t[R].fa=t[L].ch[1]=0;
else L=t[x].ch[0],R=x,t[L].fa=t[R].ch[0]=0;
for(;nrt(x);){
int y=t[x].fa;
if(t[y].ch[1]==x)t[y].ch[1]=L,t[L].fa=y,L=y;
else t[y].ch[0]=R,t[R].fa=y,R=y;
x=y;
}
t[L].fa=t[R].fa=0;
}
int merge(int x,int y){
if(!x || !y)return x|y;
if(t[x].p>t[y].p)return t[t[x].ch[1]=merge(t[x].ch[1],y)].fa=x,x;
else return t[t[y].ch[0]=merge(x,t[y].ch[0])].fa=y,y;
}
inline ui Mx(int x){return se[x].empty()?0:se[x].rbegin()->first;}
inline void mdf(int x,int y,int o){
if(o==1)se[x].insert({t[y].p,y});
else se[x].erase({t[y].p,y});
t[x].qsz+=t[y].sz2*o;
t[x].p=max(prio[x],Mx(x));
}
inline void modify(int x,int y){
dad[x]=y;
int p,q,a,b,c=0,d,e,f,ox=x,s;
f=getrt(x);a=t[f].fa;if(a)mdf(a,f,-1);
split(x,p,q,1);b=go(p,1);
for(;b;b=d){
for(c=b;d=t[c].fa,d && Mx(d)<=max(Mx(b),t[c].p);c=d);
t[d].ch[1]=0;
if(!se[b].empty())e=se[b].rbegin()->second,mdf(b,e,-1),downrot(b),c=merge(getrt(c),e),t[c].fa=0;
for(;upd(b),b!=c;b=t[b].fa);
t[c].fa=d;if(d)mdf(d,c,1);
}
if(c)t[c].fa=a;if(a && c)mdf(a,c,1);if(a)downrot(a);
for(s=0,e=x;e;e=t[e].fa)s+=t[t[e].ch[1]].sz2+t[e].qsz+1;
for(;a;a=t[a].fa){
if(t[a].fa && !nrt(a))t[t[a].fa].qsz-=s;
upd(a);
}
for(;upd(x),nrt(x);x=t[x].fa);
t[x].fa=y;
for(;a=t[x].fa,a && getmx(a)<t[x].p;){
b=getrt(a);c=t[b].fa;if(c)mdf(c,b,-1);
split(a,p,q,0);
if(q){
for(b=go(q,0);upd(b),b!=q;b=t[b].fa);
t[q].fa=a,mdf(a,q,1),uprot(a);if(t[a].p>t[p].p)p=a;
}
b=go(p,1);x=merge(p,x);t[x].fa=c;
for(;upd(b),nrt(b);b=t[b].fa);
}
if(a)mdf(a,x,1),uprot(a);
for(;a;a=t[a].fa){
if(t[a].fa && !nrt(a))t[t[a].fa].qsz+=s;
upd(a);
}
}
void ask(int u,int l,int r){
int A=t[t[u].ch[0]].sz;
if(t[u].sz2<=B && l==1 && r==t[u].sz){report(t[u].ss);return;}
if(l<=A+1 && A+1<=r)report(val[u]);
if(l<=A)ask(t[u].ch[0],l,min(r,A));
if(A+1<r)ask(t[u].ch[1],max(1,l-A-1),max(1,r-A-1));
}
inline void ask(int x,int y){
for(;;){
int tx=getrt(x),ty=getrt(y),rx=getrk(x),ry=getrk(y);
if(tx==ty){
if(rx>ry)swap(rx,ry);
ask(tx,rx,ry);break;
}else{
if(getdep(tx)<getdep(ty))swap(x,y),swap(tx,ty),swap(rx,ry);
ask(tx,1,rx);x=t[tx].fa;
}
}
}
vector<int>e[N];
ui mx[N];int ma[N];
void dfs1(int x){
mx[x]=t[x].p=prio[x]=R();t[x].sz=1;
for(int y:e[x]){
dfs1(y);upa(mx[x],mx[y]);
if(mx[y]>=mx[ma[x]])ma[x]=y;
}
for(int y:e[x])if(y!=ma[x])upa(t[x].p,mx[y]);
}
void dfs2(int x){
if(ma[x])dfs2(ma[x]);for(int y:e[x])if(y!=ma[x])dfs2(y);
if(x>1 && x==ma[dad[x]])return;
static int st[N];int w=0,ox=x;
for(;x;x=ma[x])st[++w]=x;
function<int(int,int)>dfs=[&](int l,int r){
if(l==r){t[st[l]].sz=1;t[st[l]].sz2=t[st[l]].qsz+1;t[st[l]].ss=val[st[l]];return st[l];}
int m=l;for(int i=l;i<=r;++i)if(t[st[i]].p>t[st[m]].p)m=i;
if(l<m)t[t[st[m]].ch[0]=dfs(l,m-1)].fa=st[m];
if(m<r)t[t[st[m]].ch[1]=dfs(m+1,r)].fa=st[m];
upd(st[m]);return st[m];
};
int rt=dfs(1,w);x=ox;
if(x>1)se[t[rt].fa=dad[x]].insert(make_pair(t[rt].p,rt)),t[t[rt].fa].qsz+=t[rt].sz2;
}
inline void init(int nn,int qq,vector<int>dadd,vector<infoset>vee){
n=nn;q=qq;
for(i=2;i<=n;++i)e[dad[i]=dadd[i-2]].push_back(i);
for(i=1;i<=n;++i)val[i]=vee[i-1];
//dfs1(1);t[0].ss=infoset{0,0};dfs2(1);
dfs1(1);t[0].ss=emptyset;dfs2(1);
for(auto&u:vec)u.first=-getdep(u.second);
sort(vec.begin(),vec.end());
vec.erase(unique(vec.begin(),vec.end()),vec.end());
for(auto u:vec)upd(u.second);
}
}
void init(int id,int n,int q,vector<int>dad,vector<infoset>ve){
zx2003::init(n,q,dad,ve);
}
void modify(int x,int y){
zx2003::modify(x,y);
}
void ask(int x,int y){
zx2003::ask(x,y);
}