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

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

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