Problem Statement

There is an undirected graph with $N$ vertices and $0$ edges. Initially, 0 is written on each vertex.
Process the following queries $Q$ times.
In the $i$-th query, $T_i, A_i, B_i$ are given.

• When $T_i = 1$
Add a new undirected edge between vertex $A_i$ and vertex $B_i$.
It is guaranteed that the graph remains simple (has no self-loops or multiple edges) after the edge is added.

• When $T_i = 2$
Add $B_i$ to the number written on every vertex (including vertex $A_i$) in the connected component containing vertex $A_i$.

• When $T_i = 3$
Output the number currently written on vertex $A_i$.

Input

$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$ is one of $1,2,3$

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

Output

For all queries with $T_i=3$, output the answer, one per line.

Sample

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