题目描述
Input Format
Let the i-th query query_i, the input format is following:
<dl> <dt>N Q</dt> <dt>p_0 a_0</dt> <dt>p_1 a_1</dt> <dd> <dl> <dt>:</dt> <dt>p_{N - 1} a_{N - 1}</dt> <dt>query_0</dt> <dt>query_1</dt> <dd>:query_{Q - 1}</dd> </dl> </dd> </dl>
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:
<dl> <dt>N Q</dt> <dt>p_0 a_0</dt> <dt>p_1 a_1</dt> <dd> <dl> <dt>:</dt> <dt>p_{N - 1} a_{N - 1}</dt> <dt>query_0</dt> <dt>query_1</dt> <dd>:query_{Q - 1}</dd> </dl> </dd> </dl>
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
输入格式
见题面
输出格式
见题面