#include"long.h"
#include<bits/stdc++.h>
using namespace std;
namespace zx2003{
typedef unsigned ui;
inline void upa(ui&a,ui b){a<b?a=b:0;}
mt19937 R(114514);
const int N=1e5+5,B=300;
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 rupd(int x){
	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);
	}
}
vector<pair<int,int>>vec;
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;
	vec.push_back({0,x});
}
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){
	vec.clear();
	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);
	}
	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)rupd(u.second);
}
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=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)rupd(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);
}