Problem: Input Format

Let the i-th query query_i, the input format is following:



N Q
p_0 a_0
p_1 a_1
:   :
p_{N - 1} a_{N - 1}
query_0
query_1
:   :
query_{Q - 1}


THe format of query_i is one of the three format:



1 v_i d_i x_i



2 v_i d_i



3 pr_i ar_i


Output Format

Print the result in one line for each query 2.


Constraints

* N ≤ 400000
* Q ≤ 50000
* p_i < i for all valid i.
* In each question 1 or 2, worker v_i exists.
* d_i ≤ 400000
* 0 ≤ a_i, x_i ≤ 1000



Scoring

Subtask 1 [170 points]


* N, Q ≤ 5000

Subtask 2 [310 points]


* p_i + 1 = i for all valid i.

Subtask 3 [380 points]


* There are no query 3.

Subtask 4 [590 points]


* There are no additional constraints.



Sample Input 1


6 7
-1 6
0 5
0 4
2 3
2 2
1 1
2 0 1
1 0 2 1
2 2 1
3 3 3
2 0 3
3 3 4
2 1 1


Sample Output 1


15
12
30
8

Output Format

Print the result in one line for each query 2.


Constraints

* N ≤ 400000
* Q ≤ 50000
* p_i < i for all valid i.
* In each question 1 or 2, worker v_i exists.
* d_i ≤ 400000
* 0 ≤ a_i, x_i ≤ 1000



Scoring

Subtask 1 [170 points]


* N, Q ≤ 5000

Subtask 2 [310 points]


* p_i + 1 = i for all valid i.

Subtask 3 [380 points]


* There are no query 3.

Subtask 4 [590 points]


* There are no additional constraints.

Input Format

Let the i-th query query_i, the input format is following:



N Q
p_0 a_0
p_1 a_1
:   :
p_{N - 1} a_{N - 1}
query_0
query_1
:   :
query_{Q - 1}


THe format of query_i is one of the three format:



1 v_i d_i x_i



2 v_i d_i



3 pr_i ar_i

Example

Input

6 7
-1 6
0 5
0 4
2 3
2 2
1 1
2 0 1
1 0 2 1
2 2 1
3 3 3
2 0 3
3 3 4
2 1 1


Output

15
12
30
8

Solution (in CPP):

Solution:
#include <algorithm>  
#include <iostream>  
#include <sstream>  
#include <string>  
#include <cstring>
#include <vector>  
#include <queue>  
#include <set>  
#include <map>  
#include <cstdio>  
#include <cstdlib>  
#include <cctype>  
#include <cmath>  
#include <list>  
#include <cassert>
#include <ctime>
#include <climits>
using namespace std;  
 
#define PB push_back  
#define MP make_pair  
#define SZ(v) ((int)(v).size())  
#define FOR(i,a,b) for(int i=(a);i<(b);++i)  
#define REP(i,n) FOR(i,0,n)  
#define FORE(i,a,b) for(int i=(a);i<=(b);++i)  
#define REPE(i,n) FORE(i,0,n)  
#define FORSZ(i,a,v) FOR(i,a,SZ(v))  
#define REPSZ(i,v) REP(i,SZ(v))  
typedef long long ll;
typedef unsigned long long ull;
ll gcd(ll a,ll b) { return b==0?a:gcd(b,a%b); }
 
const int MAXN=400000;
const int MAXQ=50000;
const int MAXEMP=MAXN+MAXQ;
const int SZ=400;
const int MAXB=(MAXEMP+SZ-1)/SZ;
 
int n,nq,nemp;
int par[MAXEMP],oval[MAXEMP]; bool alive[MAXEMP];
int qt[MAXQ],qemp[MAXQ],qd[MAXQ],qby[MAXQ];
 
int chead[MAXEMP],cnxt[MAXEMP];
int d[MAXEMP],lid[MAXEMP],rid[MAXEMP],emp[MAXEMP],nid;
void dfs(int at) {
	d[at]=par[at]==-1?0:d[par[at]]+1; emp[nid]=at,lid[at]=nid++;
	for(int to=chead[at];to!=-1;to=cnxt[to]) dfs(to);
	rid[at]=nid-1;
}
 
int pos[MAXEMP];
int sd[MAXEMP];

typedef struct S {
	ll sval[4*SZ]; int slazy[4*SZ]; int scnt[4*SZ];
	void clear() {
		memset(sval,0,sizeof(sval)); memset(slazy,0,sizeof(slazy)); memset(scnt,0,sizeof(scnt));
	}
	void spush(int x) {
		if(slazy[x]==0) return;
		sval[2*x+1]+=slazy[x]*scnt[2*x+1]; slazy[2*x+1]+=slazy[x];
		sval[2*x+2]+=slazy[x]*scnt[2*x+2]; slazy[2*x+2]+=slazy[x];
		slazy[x]=0;
	}
	void scalc(int x) { scnt[x]=scnt[2*x+1]+scnt[2*x+2]; sval[x]=sval[2*x+1]+sval[2*x+2]; }
	void sborn(int x,int l,int r,int IDX,int VAL) {
		if(l==r) {
			sval[x]=VAL,slazy[x]=0,scnt[x]=1;
		} else {
			spush(x);
			int m=l+(r-l)/2;
			if(IDX<=m) sborn(2*x+1,l,m,IDX,VAL); else sborn(2*x+2,m+1,r,IDX,VAL);
			scalc(x);
		}
		//printf("sborn(%d,%d,%d,%d,%d) -> %d %lld\n",x,l,r,IDX,VAL,scnt[x],sval[x]);
	}
	void smod(int x,int l,int r,int L,int R,int BY) {
		if(L<=l&&r<=R) {
			sval[x]+=(ll)scnt[x]*BY;
			slazy[x]+=BY;
		} else {
			spush(x);
			int m=l+(r-l)/2;
			if(L<=m) smod(2*x+1,l,m,L,R,BY);
			if(m+1<=R) smod(2*x+2,m+1,r,L,R,BY);
			scalc(x);
		}
		//printf("smod(%d,%d,%d,%d,%d,%d) -> %d %lld %d\n",x,l,r,L,R,BY,scnt[x],sval[x],slazy[x]);
	}
	ll sget(int x,int l,int r,int L,int R) {
		if(L<=l&&r<=R) {
			return sval[x];
		} else {
			spush(x);
			int m=l+(r-l)/2; ll ret=0;
			if(L<=m) ret+=sget(2*x+1,l,m,L,R);
			if(m+1<=R) ret+=sget(2*x+2,m+1,r,L,R);
			return ret;
		}
	}
} S;
S s[MAXB];


int nb;
pair<int,int> tmp[SZ];
void build() {
	for(int i=0;i<nemp;i+=SZ) {
		int cnt=min(SZ,nemp-i);
		REP(j,cnt) tmp[j]=MP(d[emp[i+j]],emp[i+j]);
		sort(tmp,tmp+cnt);
		REP(j,cnt) sd[i+j]=tmp[j].first,pos[tmp[j].second]=i+j;
	}
	nb=(nemp+SZ-1)/SZ;
	REP(i,nb) s[i].clear();
	REP(i,nemp) if(alive[i]) s[pos[i]/SZ].sborn(0,0,SZ-1,pos[i]%SZ,oval[i]);
	//REP(i,nemp) printf("%d: emp=%d d=%d pos=%d oval=%d\n",i,emp[i],d[emp[i]],pos[emp[i]],oval[emp[i]]);
	//REP(i,nemp) printf(" %d",sd[i]); puts("");
}
 
ll query1(int idx,int ld,int rd) {
	//printf("query1(%d,%d,%d)\n",idx,ld,rd);
	if(!alive[idx]||d[idx]<ld||d[idx]>=rd) return 0;
	return s[pos[idx]/SZ].sget(0,0,SZ-1,pos[idx]%SZ,pos[idx]%SZ);
}
 
ll queryb(int idx,int ld,int rd) {
	//printf("queryb(%d,%d,%d)\n",idx,ld,rd);
	int bl=idx*SZ,br=min(nemp,(idx+1)*SZ);
	int l=lower_bound(sd+bl,sd+br,ld)-sd;
	if(l>=br||sd[l]>=rd) return 0;
	int r=lower_bound(sd+bl,sd+br,rd)-sd;
	//printf("->%d..%d (%d,%d)\n",l,r-1,bl,br);
	return s[idx].sget(0,0,SZ-1,l%SZ,(r-1)%SZ);
}
 
ll query(int lid,int rid,int ld,int rd) {
	//printf("query(%d..%d,%d..%d)\n",lid,rid,ld,rd);
	ll ret=0;
	while(lid<rid&&lid%SZ!=0) ret+=query1(emp[lid++],ld,rd);
	while(lid<rid&&rid%SZ!=0) ret+=query1(emp[--rid],ld,rd);
	while(lid<rid) ret+=queryb(lid/SZ,ld,rd),lid+=SZ;
	return ret;
}
 
void update1(int idx,int ld,int rd,int by) {
	if(!alive[idx]||d[idx]<ld||d[idx]>=rd) return;
	s[pos[idx]/SZ].smod(0,0,SZ-1,pos[idx]%SZ,pos[idx]%SZ,by);
}
 
void updateb(int idx,int ld,int rd,int by) {
	int bl=idx*SZ,br=min(nemp,(idx+1)*SZ);
	int l=lower_bound(sd+bl,sd+br,ld)-sd;
	if(l>=br||sd[l]>=rd) return;
	int r=lower_bound(sd+bl,sd+br,rd)-sd;
	return s[idx].smod(0,0,SZ-1,l%SZ,(r-1)%SZ,by);
}
 
void update(int lid,int rid,int ld,int rd,int by) {
	while(lid<rid&&lid%SZ!=0) update1(emp[lid++],ld,rd,by);
	while(lid<rid&&rid%SZ!=0) update1(emp[--rid],ld,rd,by);
	while(lid<rid) updateb(lid/SZ,ld,rd,by),lid+=SZ;
}
 
void born(int idx) {
	assert(!alive[idx]); alive[idx]=true;
	s[pos[idx]/SZ].sborn(0,0,SZ-1,pos[idx]%SZ,oval[idx]);
}
 
ll ans[MAXQ];
void solve() {
	REP(i,nemp) chead[i]=-1; REP(i,nemp) if(par[i]!=-1) cnxt[i]=chead[par[i]],chead[par[i]]=i;
	nid=0; dfs(0); build();
 
	REP(i,nq) {
		if(qt[i]==1) update(lid[qemp[i]],rid[qemp[i]]+1,d[qemp[i]],d[qemp[i]]+qd[i]+1,qby[i]);
		if(qt[i]==2) ans[i]=query(lid[qemp[i]],rid[qemp[i]]+1,d[qemp[i]],d[qemp[i]]+qd[i]+1);
		if(qt[i]==3) born(qemp[i]);
	}
}
 
void run() {
	scanf("%d%d",&n,&nq); nemp=n;
	REP(i,n) scanf("%d%d",&par[i],&oval[i]),alive[i]=true;
	REP(i,nq) {
		scanf("%d",&qt[i]);
		if(qt[i]==1) scanf("%d%d%d",&qemp[i],&qd[i],&qby[i]);
		if(qt[i]==2) scanf("%d%d",&qemp[i],&qd[i]);
		if(qt[i]==3) scanf("%d%d",&par[nemp],&oval[nemp]),alive[nemp]=false,qemp[i]=nemp++;
	}
	solve();
	REP(i,nq) if(qt[i]==2) printf("%lld\n",ans[i]);
}
 
void stress() {
	REP(x,10) {
		n=MAXN; nq=MAXQ;
		par[0]=-1; FOR(i,1,n) par[i]=i<n/10?i-1:(rand()*1000+rand())%(n/10); REP(i,n) oval[i]=rand()%1000+1,alive[i]=true; nemp=n;
		REP(i,nq) {
			qt[i]=rand()%3+1;
			if(qt[i]==1) qemp[i]=0,qd[i]=rand()%(n/10),qby[i]=rand()%1000+1;
			if(qt[i]==2) qemp[i]=0,qd[i]=rand()%(n/10);
			if(qt[i]==3) qemp[i]=nemp,par[nemp]=(rand()*1000+rand())%(n/10),oval[nemp]=rand()%1000+1,alive[nemp]=false,++nemp;
		}
		clock_t begin = clock();
		solve();
		printf("%.9lf\n",double(clock() - begin) / CLOCKS_PER_SEC);
	}
}
 
int main() {
	//stress();
	run();
	return 0;
}