square869120Contest #4 - Get the Salary of Atcoder

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

Source: atcoder | Difficulty: UNKNOWN_DIFFICULTY


Solutions: