Contest Duration: - (local time) (200 minutes)
G - Get the Salary of Atcoder /

Time Limit: 2.5 sec / Memory Limit: 1024 MB

Max Score: 1450 Points

### Problem Statement

There are N workers in Atcoder company. Each worker is numbered 0 through N - 1, and the boss for worker i is p_i like a tree structure and the salary is currently a_i. (p_i < i, especially p_0 = -1 because worker 0 is a president)
In atcoder, the boss of boss of boss of ... (repeated k times) worker i called "k-th upper boss", and "k-th lower subordinate" called for vice versa.

You have to process Q queries for Atcoder:
• Query 1: You are given v_i, d_i, x_i. Increase the salary of worker v_i, and all j-th (1 ≤ j ≤ d_i) lower subordinates by x_i.
• Query 2: You are given v_i, d_i. Calculate the sum of salary of worker v_i and all j-th (1 ≤ j ≤ d_i) lower subordinates.
• Query 3: You are given pr_i, ar_i. Now Atcoder has a new worker c! (c is the current number of workers) The boss is pr_i, and the first salary is ar_i.
Process all queries!!!

### 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

• N, Q ≤ 5000
• p_i + 1 = i for all valid i.
• There are no query 3.
• 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


### Sample Input 2

7 9
-1 1
0 5
0 7
0 8
1 3
4 1
5 1
2 1 1
2 1 2
1 1 2 3
1 4 1 1
2 3 1
2 0 2
3 6 1
3 7 11
2 0 15


### Sample Output 2

8
9
8
31
49


### 問題文

また、Atcoderでは、社員 i の上司の上司の上司の...上司 (k 回繰り返されるとする) を 「k 個上の上司」とし、その逆は「k 個下の部下」と呼ばれている。
また、次のような処理 / 質問を合計 Q 個処理しなければなりません。
• タイプ1：v_i, d_i, x_i が与えられ、社員 v_i と、この j (1 ≤ j ≤ d_i) 個下の部下全員に対し、給料を x_i 上げる。(x_i は負のときもある)
• タイプ2：v_i, d_i が与えられ、社員 v_i と、この j (1 ≤ j ≤ d_i) 個下の部下全員の給料の合計を求める。
• タイプ3：pr_i, ar_i が与えられ、現在の社員数を c としたときに新入社員 cpr_i の直接の部下として配置する。また最初の給料を ar_i とする。
そのとき、すべての質問に答えなさい。

### 入力

i 番目の処理 / 質問を query_i としたとき、次のような形式で与えられる。
N Q
p_0 a_0
p_1 a_1
:   :
p_{N - 1} a_{N - 1}
query_0
query_1
:   :
query_{Q - 1}

また、query_i は、次の3つの形式のどれかで与えられる。
1 v_i d_i x_i

2 v_i d_i

3 pr_i ar_i


### 制約

• N ≤ 400000
• Q ≤ 50000
• p_i < i が常に成立する
• それぞれの処理 / 質問に対し、社員 v_i はその時点で存在する
• d_i ≤ 400000
• 0 ≤ a_i, x_i ≤ 1000

### 得点

• N, Q ≤ 5000

• p_i + 1 = i がすべての i に対して成立する。

• タイプ3のクエリは存在しない。

• 追加の制約はない。

### 入力例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


### 出力例1

15
12
30
8


### 入力例2

7 9
-1 1
0 5
0 7
0 8
1 3
4 1
5 1
2 1 1
2 1 2
1 1 2 3
1 4 1 1
2 3 1
2 0 2
3 6 1
3 7 11
2 0 15


### 出力例2

8
9
8
31
49