There is a forest consisting of $N$ vertices. The vertices are numbered $1$ through $N$, and there are no edges. Every vertex $v$ has an integer $X_v$, initially $X_v = 1$.

Write a program that executes the following queries:

• 1 $a$ $b$ $c$: Connect vertices $a$ and $b$ with an edge of weight $c$. The input guarantees that the result of the query remains a forest.
• 2 $a$ $b$: Remove the edge connecting vertices $a$ and $b$. The input guarantees that there is an edge between the two vertices.
• 3 $a$: Change $X_a$ to $1 - X_a$. Then, in the tree containing $a$, compute the following: Let the vertices of the tree be $v_1, v_2, \dots, v_k$. Compute and output $\min_{1 \le i \le k}{\left\{ \sum_{1 \le j \le k}{dist(v_i, v_j) \times X_{v_j}} \right\}}$, where $dist(v_i, v_j)$ is the sum of the weights of all edges on the path from $v_i$ to $v_j$.

Input

The first line contains the number of vertices $N$ and the number of queries $Q$. The next $Q$ lines each contain one query.

The vertex numbers given in the queries ($a$, $b$ for type 1 and 2 queries, $a$ for type 3 queries) are encrypted and must be decrypted before executing the query. If the given vertex number is $x$ and the value obtained from the previous type 3 query is $S$, then the decrypted vertex number is $(x - 1 + S) \bmod N + 1$.

Output

For each type 3 query, output the computed value on a separate line in the order the queries are given.

Constraints

• $1 \le N \le 10^5$
• $1 \le Q \le 3 \times 10^5$
• $1 \le a, b \le N$
• $a \ne b$
• $1 \le c \le 10^8$

Examples

Input 1

3 7
1 1 2 3
1 3 1 1
3 1
2 1 3
3 1
1 2 1 2
3 2

Output 1

4
0
0

Input 2

5 17
1 1 5 10
1 3 1 7
1 5 2 5
1 3 4 2
2 3 1
1 4 1 6
2 5 2
3 1
3 2
3 2
1 2 1 2
3 4
2 5 1
1 4 5 2
2 3 4
1 3 5 9
3 5

Output 2

18
2
0
0
9

Input 3

10 37
1 2 3 6428496
1 7 10 41603701
1 2 7 61903527
1 1 6 57606292
1 2 1 43682226
1 8 2 59090781
3 6
3 10
1 10 7 15269842
3 6
3 7
1 3 10 39799671
1 3 5 28501778
3 5
2 1 10
1 6 10 37641690
2 9 6
3 8
1 6 8 89420938
3 9
2 6 3
1 9 6 17757145
2 9 3
1 1 9 26575112
2 3 8
1 2 1 19670627
2 3 5
1 1 5 12760556
2 3 4
1 4 1 36949637
3 7
2 6 9
1 6 8 74850387
2 3 8
3 3
1 7 3 77007154
3 3

Output 3

274612258
215521477
187109093
171839251
211638922
68332023
151324465
224010174
0
223740409