题目描述

输入格式

$i$ 番目の処理 / 質問を $query_i$ としたとき、次のような形式で与えられる。

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

また、$query_i$ は、次の3つの形式のどれかで与えられる。

1 $v_i$ $d_i$ $x_i$

2 $v_i$ $d_i$

3 $pr_i$ $ar_i$

输出格式

各質問2に対し、答えをそれぞれ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

15
12
30
8

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

8
9
8
31
49

提示

制約

• $N\ <\ =\ 400000$
• $Q\ <\ =\ 50000$
• $p_i\ が常に成立する$
• それぞれの処理 / 質問に対し、社員 $v_i$ はその時点で存在する
• $d_i\ <\ =\ 400000$
• $0\ <\ =\ a_i,\ x_i\ <\ =\ 1000$

得点

小課題1 [$170$ 点]

• $N,\ Q\ <\ =\ 5000$

小課題2 [$310$ 点]

• $p_i\ +\ 1\ =\ i$ がすべての $i$ に対して成立する。

小課題4 [$380$ 点]

• タイプ3のクエリは存在しない。

小課題5 [$590$ 点]

• 追加の制約はない。