問題文

$N$頂点$0$辺の無向グラフがあります。各頂点には最初0が書かれています。
以下のクエリを$Q$回処理してください。
$i$回目のクエリでは$T_i, A_i, B_i$が与えられます。

• $T_i = 1$のとき
頂点$A_i$と頂点$B_i$の間に新たな無向辺を追加します。
辺の追加後もグラフは単純(自己ループと多重辺を持たない)であることが保証されます。

• $T_i = 2$のとき
頂点$A_i$を含む連結成分内の全ての頂点(頂点$A_i$を含む)に書かれている数に$B_i$を足します。

• $T_i = 3$のとき
現在頂点$A_i$に書かれている数を出力します。

入力

$N\ Q$
$T_1\ A_1\ B_1$
$T_2\ A_2\ B_2$
$T_3\ A_3\ B_3$
$\hspace{16pt}\vdots$
$T_Q\ A_Q\ B_Q$

$1 \le N \le 5 \times 10^5$
$1 \le Q \le 5 \times 10^5$
$T_i$は$1,2,3$のいずれか

• $T_i = 1$のとき : $1 \le A_i \le N, 1 \le B_i \le N$
• $T_i = 2$のとき : $1 \le A_i \le N, -2000 \le B_i \le 2000$
• $T_i = 3$のとき : $1 \le A_i \le N, B_i = 0$

出力

$T_i=3$であるようなクエリ全てに対する答えを一行ずつ出力してください。

サンプル

3 9
2 1 10
3 1 0
1 1 2
2 2 20
1 1 3
2 2 40
3 1 0
3 2 0
3 3 0

10
70
60
40

8 28
2 3 17
2 7 25
1 3 8
2 5 11
1 1 7
2 7 35
3 7 0
3 8 0
1 4 2
2 2 42
2 3 34
3 8 0
3 4 0
3 2 0
1 5 1
1 1 6
1 6 5
2 6 53
1 6 7
1 6 2
2 4 11
3 1 0
1 4 6
3 7 0
1 3 7
2 1 50
3 8 0
3 3 0

60
0
34
42
42
99
124
84
101

1 3
3 1 0
2 1 10
3 1 0

0
10