C++ :

//#pragma GCC optimize(2)
#include<cstdio>
#include<algorithm>
#include<cmath>
#define L 1<<23
#define C (c=*A++)
#define NES //__attribute__((optimize("-O2"))) __inline__ __attribute__((always_inline))
#define ENS //__attribute__((optimize("-O2")))
#define N 100001
#define Q 401

using namespace std;int n,test,et=1,li[N],lr[Q<<1],rl[Q<<1],tl,d[N],e[N],we[N],nt[N],f[N*41],S[128],cnt,g[N],w[N],*s,l[Q],t[Q],G[Q],p[N],le[Q],ri[Q],last[N],b[N],wt,ss[19];char fl[L],*A=fl;
NES void read(int&x){char c;for(x=0;'0'>C||c>'9';);while('0'<=c&&c<='9')x=(x<<3)+(x<<1)+c-48,C;}NES void print(int x){if(!x)*A++=(48);else{for(wt=0;x;ss[++wt]=x%10,x/=10);for(;wt;*A++=(ss[wt--]+48));}}
struct ques
{int F,x,tmp;NES void add(){g[p[x]]+=tmp,g[last[x]]+=tmp;}
	ENS void query()
	{
		if(F==1)
		{int i,mid,lq=2147483647,rq,lf,rf,j,l1,l2,lim;lf=p[x],rf=last[x];if(tmp>rf-lf+1)return(void)(*A++='-',*A++='1',*A++='\n');
			if(b[lf]==b[rf]){for(l1=t[b[lf]],tl=0,i=lf;i<=rf;lr[++tl]=w[i]+l1,i++);nth_element(lr+1,lr+tmp,lr+tl+1),print(lr[tmp]),*A++='\n';}
			else
			{for(rq=0,i=b[lf]+1;i<b[rf];i++){if(rq<t[i]+G[i])rq=t[i]+G[i];if(t[i]<lq)lq=t[i];}
//				if(rf-le[b[rf]]+ri[b[lf]]-lf<127,true){
				for(l1=t[b[lf]],l2=t[b[rf]],tl=0,i=lf;i<ri[b[lf]];lr[++tl]=w[i]+l1,i++);for(i=le[b[rf]];i<=rf;lr[++tl]=w[i]+l2,i++);sort(lr+1,lr+tl+1);//}
/*				else
					if((t[b[lf]]+G[b[lf]]>t[b[rf]]+G[b[rf]]?t[b[lf]]+G[b[lf]]:t[b[rf]]+G[b[rf]])<=(1<<14))
					{
						for(l1=t[b[lf]],l2=t[b[rf]],tl=0,i=lf;i<ri[b[lf]];lr[++tl]=w[i]+l1,i++);for(i=le[b[rf]];i<=rf;lr[++tl]=w[i]+l2,i++);
						for(i=0;i<=120;S[i]=0,S[i+1]=0,S[i+2]=0,S[i+3]=0,S[i+4]=0,S[i+5]=0,S[i+6]=0,S[i+7]=0,i+=8);for(;i<=127;S[i++]=0);
						for(i=1;i<=tl;S[lr[i++]&127]++);for(i=1;i<=127;S[i]+=S[i-1],i++);for(i=tl;i;rl[S[lr[i]&127]--]=lr[i],i--);
						for(i=0;i<=120;S[i]=0,S[i+1]=0,S[i+2]=0,S[i+3]=0,S[i+4]=0,S[i+5]=0,S[i+6]=0,S[i+7]=0,i+=8);for(;i<=127;S[i++]=0);
						for(i=1;i<=tl;S[rl[i++]>>7]++);for(i=1;i<=127;S[i]+=S[i-1],i++);for(i=tl;i;lr[S[rl[i]>>7]--]=rl[i],i--);
					}
					else
					{
						for(l1=t[b[lf]],l2=t[b[rf]],tl=0,i=lf;i<ri[b[lf]];rl[++tl]=w[i]+l1,i++);for(i=le[b[rf]];i<=rf;rl[++tl]=w[i]+l2,i++);
						for(i=0;i<=120;S[i]=0,S[i+1]=0,S[i+2]=0,S[i+3]=0,S[i+4]=0,S[i+5]=0,S[i+6]=0,S[i+7]=0,i+=8);for(;i<=127;S[i++]=0);
						for(i=1;i<=tl;S[rl[i++]&127]++);for(i=1;i<=127;S[i]+=S[i-1],i++);for(i=tl;i;lr[S[rl[i]&127]--]=rl[i],i--);
						for(i=0;i<=120;S[i]=0,S[i+1]=0,S[i+2]=0,S[i+3]=0,S[i+4]=0,S[i+5]=0,S[i+6]=0,S[i+7]=0,i+=8);for(;i<=127;S[i++]=0);
						for(i=1;i<=tl;S[lr[i++]>>7&127]++);for(i=1;i<=127;S[i]+=S[i-1],i++);for(i=tl;i;rl[S[lr[i]>>7&127]--]=lr[i],i--);
						for(i=0;i<=120;S[i]=0,S[i+1]=0,S[i+2]=0,S[i+3]=0,S[i+4]=0,S[i+5]=0,S[i+6]=0,S[i+7]=0,i+=8);for(;i<=127;S[i++]=0);
						for(i=1;i<=tl;S[rl[i++]>>14]++);for(i=1;i<=127;S[i]+=S[i-1],i++);for(i=tl;i;lr[S[rl[i]>>14]--]=rl[i],i--);
					}*/if(tl<tmp){if(lr[tl]>rq)rq=lr[tl];}else if(tl=tmp,lr[tl]<rq||!rq)rq=lr[tl];
				for(lq=lq>lr[1]?lr[1]:lq;lq<rq;)
				{int tp=0,lw,rw,mi;
					if(mid=(lq+rq)>>1,mid>lr[tl])tp=tl;else if(mid>=lr[1]){for(lw=1,rw=tl+1;lw<rw-1;lr[mi=(lw+rw)>>1]<=mid?lw=mi:rw=mi);tp=lw;}
					for(i=b[lf]+1;i+8<b[rf]&&tp<tmp;i+=8)
						tp+= (mid>=t[i]?(mid>G[i]+t[i]?ri[i]-le[i]:f[mid-t[i]+l[i]]):0)
							+(mid>=t[i+1]?(mid>G[i+1]+t[i+1]?ri[i+1]-le[i+1]:f[mid-t[i+1]+l[i+1]]):0)
							+(mid>=t[i+2]?(mid>G[i+2]+t[i+2]?ri[i+2]-le[i+2]:f[mid-t[i+2]+l[i+2]]):0)
							+(mid>=t[i+3]?(mid>G[i+3]+t[i+3]?ri[i+3]-le[i+3]:f[mid-t[i+3]+l[i+3]]):0)
							+(mid>=t[i+4]?(mid>G[i+4]+t[i+4]?ri[i+4]-le[i+4]:f[mid-t[i+4]+l[i+4]]):0)
							+(mid>=t[i+5]?(mid>G[i+5]+t[i+5]?ri[i+5]-le[i+5]:f[mid-t[i+5]+l[i+5]]):0)
							+(mid>=t[i+6]?(mid>G[i+6]+t[i+6]?ri[i+6]-le[i+6]:f[mid-t[i+6]+l[i+6]]):0)
							+(mid>=t[i+7]?(mid>G[i+7]+t[i+7]?ri[i+7]-le[i+7]:f[mid-t[i+7]+l[i+7]]):0);
					for(;i<b[rf]&&tp<tmp;tp+=mid>=t[i]?(mid>G[i]+t[i]?ri[i]-le[i]:f[mid-t[i]+l[i]]):0,i++);
					if(tp<tmp)lq=mid+1;else rq=mid;
				}print(rq),*A++=('\n');
			}
		}
		else
		{int lf,rf,j,i;lf=p[x],rf=last[x];
			if(b[lf]==b[rf])for(G[b[lf]]+=tmp,s=&f[l[b[lf]]],i=lf;i<=rf;w[i]+=tmp,i++)for(j=w[i];j<w[i]+tmp;s[j++]--);
			else
				switch(tmp)
				{
					case 0:break;
					case 1:
						for(G[b[lf]]++,s=&f[l[b[lf]]],i=lf;i<ri[b[lf]];s[w[i]]--,w[i]++,i++);
						for(i=b[lf]+1;i<b[rf];t[i]+=tmp,i++);
						for(G[b[rf]]++,s=&f[l[b[rf]]],i=le[b[rf]];i<=rf;s[w[i]]--,w[i]++,i++);break;
					case 2:
						for(G[b[lf]]+=2,s=&f[l[b[lf]]],i=lf;i<ri[b[lf]];s[w[i]]--,s[w[i]+1]--,w[i]+=2,i++);
						for(i=b[lf]+1;i<b[rf];t[i]+=tmp,i++);
						for(G[b[rf]]+=2,s=&f[l[b[rf]]],i=le[b[rf]];i<=rf;s[w[i]]--,s[w[i]+1]--,w[i]+=2,i++);break;
					case 3:
						for(G[b[lf]]+=3,s=&f[l[b[lf]]],i=lf;i<ri[b[lf]];j=w[i],s[j]--,s[j+1]--,s[j+2]--,w[i]+=3,i++);
						for(i=b[lf]+1;i<b[rf];t[i]+=tmp,i++);
						for(G[b[rf]]+=3,s=&f[l[b[rf]]],i=le[b[rf]];i<=rf;j=w[i],s[j]--,s[j+1]--,s[j+2]--,w[i]+=3,i++);break;
					case 4:
						for(G[b[lf]]+=4,s=&f[l[b[lf]]],i=lf;i<ri[b[lf]];j=w[i],s[j]--,s[j+1]--,s[j+2]--,s[j+3]--,w[i]+=4,i++);
						for(i=b[lf]+1;i<b[rf];t[i]+=tmp,i++);
						for(G[b[rf]]+=4,s=&f[l[b[rf]]],i=le[b[rf]];i<=rf;j=w[i],s[j]--,s[j+1]--,s[j+2]--,s[j+3]--,w[i]+=4,i++);break;
					case 5:
						for(G[b[lf]]+=5,s=&f[l[b[lf]]],i=lf;i<ri[b[lf]];j=w[i],s[j]--,s[j+1]--,s[j+2]--,s[j+3]--,s[j+4]--,w[i]+=5,i++);
						for(i=b[lf]+1;i<b[rf];t[i]+=tmp,i++);
						for(G[b[rf]]+=5,s=&f[l[b[rf]]],i=le[b[rf]];i<=rf;j=w[i],s[j]--,s[j+1]--,s[j+2]--,s[j+3]--,s[j+4]--,w[i]+=5,i++);break;
					case 6:
						for(G[b[lf]]+=6,s=&f[l[b[lf]]],i=lf;i<ri[b[lf]];j=w[i],s[j]--,s[j+1]--,s[j+2]--,s[j+3]--,s[j+4]--,s[j+5]--,w[i]+=6,i++);
						for(i=b[lf]+1;i<b[rf];t[i]+=tmp,i++);
						for(G[b[rf]]+=6,s=&f[l[b[rf]]],i=le[b[rf]];i<=rf;j=w[i],s[j]--,s[j+1]--,s[j+2]--,s[j+3]--,s[j+4]--,s[j+5]--,w[i]+=6,i++);break;
					case 7:
						for(G[b[lf]]+=7,s=&f[l[b[lf]]],i=lf;i<ri[b[lf]];j=w[i],s[j]--,s[j+1]--,s[j+2]--,s[j+3]--,s[j+4]--,s[j+5]--,s[j+6]--,w[i]+=7,i++);
						for(i=b[lf]+1;i<b[rf];t[i]+=tmp,i++);
						for(G[b[rf]]+=7,s=&f[l[b[rf]]],i=le[b[rf]];i<=rf;j=w[i],s[j]--,s[j+1]--,s[j+2]--,s[j+3]--,s[j+4]--,s[j+5]--,s[j+6]--,w[i]+=7,i++);break;
					case 8:
						for(G[b[lf]]+=8,s=&f[l[b[lf]]],i=lf;i<ri[b[lf]];j=w[i],s[j]--,s[j+1]--,s[j+2]--,s[j+3]--,s[j+4]--,s[j+5]--,s[j+6]--,s[j+7]--,w[i]+=8,i++);
						for(i=b[lf]+1;i<b[rf];t[i]+=tmp,i++);
						for(G[b[rf]]+=8,s=&f[l[b[rf]]],i=le[b[rf]];i<=rf;j=w[i],s[j]--,s[j+1]--,s[j+2]--,s[j+3]--,s[j+4]--,s[j+5]--,s[j+6]--,s[j+7]--,w[i]+=8,i++);break;
					case 9:
						for(G[b[lf]]+=9,s=&f[l[b[lf]]],i=lf;i<ri[b[lf]];j=w[i],s[j]--,s[j+1]--,s[j+2]--,s[j+3]--,s[j+4]--,s[j+5]--,s[j+6]--,s[j+7]--,s[j+8]--,w[i]+=9,i++);
						for(i=b[lf]+1;i<b[rf];t[i]+=tmp,i++);
						for(G[b[rf]]+=9,s=&f[l[b[rf]]],i=le[b[rf]];i<=rf;j=w[i],s[j]--,s[j+1]--,s[j+2]--,s[j+3]--,s[j+4]--,s[j+5]--,s[j+6]--,s[j+7]--,s[j+8]--,w[i]+=9,i++);break;
					case 10:
						for(G[b[lf]]+=10,s=&f[l[b[lf]]],i=lf;i<ri[b[lf]];j=w[i],s[j]--,s[j+1]--,s[j+2]--,s[j+3]--,s[j+4]--,s[j+5]--,s[j+6]--,s[j+7]--,s[j+8]--,s[j+9]--,w[i]+=10,i++);
						for(i=b[lf]+1;i<b[rf];t[i]+=tmp,i++);
						for(G[b[rf]]+=10,s=&f[l[b[rf]]],i=le[b[rf]];i<=rf;j=w[i],s[j]--,s[j+1]--,s[j+2]--,s[j+3]--,s[j+4]--,s[j+5]--,s[j+6]--,s[j+7]--,s[j+8]--,s[j+9]--,w[i]+=10,i++);break;
				}
		}
	}
}q[N];
NES void dfs(int x){if(e[x])li[++tl]=e[x],w[p[e[x]]=++cnt]=d[e[x]]=d[x]+we[e[x]],e[x]=nt[e[x]];else last[x]=cnt,tl--;}
ENS int main()
{int i,x,y,S,mx,mi;
	for(fl[fread(fl,1,L,stdin)]=EOF,read(n),read(test),read(x),x=2;x<=n;read(y),read(we[x]),nt[x]=e[y],e[y]=x,x++);
	for(S=sqrt(n),li[tl=1]=1,p[1]=cnt=1;tl;dfs(li[tl]));
	for(i=test;i;i--)if(read(q[i].F),q[i].F==1)read(q[i].x),read(q[i].tmp);else read(q[i].x),read(q[i].tmp),q[i].add();
	for(le[cnt=x=0]=1,ri[x=0]=S+1;ri[x]<=n;le[x+1]=ri[x],ri[x+1]=ri[x]+S,x++)
	{mx=-2147483647,mi=2147483647,y=0;
		for(l[x]=cnt,i=le[x];i<ri[x];b[i]=x,y+=g[i],i++){if(mi>w[i])mi=w[i];if(mx<w[i])mx=w[i];}
		for(cnt+=mx+y-(t[x]=mi)+1,G[x]=mx-mi,i=le[x];i<ri[x];f[l[x]+(w[i]-=mi)]++,i++);for(i=l[x]+1;i<cnt;f[i]+=f[i-1],i++);
	}mx=-2147483647,mi=2147483647,y=0;
	for(ri[x]=n+1,l[x]=cnt,i=le[x];i<ri[x];b[i]=x,y+=g[i],i++){if(mi>w[i])mi=w[i];if(mx<w[i])mx=w[i];}
	for(cnt+=mx+y-(t[x]=mi)+1,G[x]=mx-mi,i=le[x];i<ri[x];f[l[x]+(w[i]-=mi)]++,i++);for(i=l[x]+1;i<cnt;f[i]+=f[i-1],i++);
	for(A=fl;test;q[test].query(),test--);fwrite(fl,1,A-fl,stdout);
}