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

inputFormat

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

outputFormat

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

样例

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

15
12
30
8

</p>