Problem Description

Input Format

When the $i$-th operation/query is denoted as $query_i$, it is given in the following format:

$ N $ $ Q $ $ p_0 $ $ a_0 $ $ p_1 $ $ a_1 $ : : $p_{N\ -\ 1}$ $a_{N\ -\ 1}$ $ query_0 $ $ query_1 $ : : $query_{Q\ -\ 1}$

Also, $query_i$ is given in one of the following three formats:

1 $ v_i $ $ d_i $ $ x_i $

2 $ v_i $ $ d_i $

3 $ pr_i $ $ ar_i $

Output Format

For each query of type 2, output the answer in a separate line.

Sample Input and Output

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

Notes/Hints

Constraints

• $N\ \leq\ 400000$
• $Q\ \leq\ 50000$
• $ p_i $ always holds
• For each operation/query, employee $ v_i $ exists at that point
• $d_i\ \leq\ 400000$
• $0\ \leq\ a_i,\ x_i\ \leq\ 1000$

Scoring

Subtask 1 [$ 170 $ points]

• $N,\ Q\ \leq\ 5000$

Subtask 2 [$ 310 $ points]

• $p_i\ +\ 1\ =\ i$ holds for all $ i $

Subtask 4 [$ 380 $ points]

• No type 3 queries exist

Subtask 5 [$ 590 $ points]

• No additional constraints

见题面 Input 部分

见题面 Output 部分