Tree and Queries 20

Time limit5sMemory limit512 MB

Summary

Maintain a dynamic forest with link/cut and weighted edges, supporting toggling a vertex weight and querying the minimum weighted sum of tree distances from any vertex, with encrypted vertex indices.

Level: Hard10 of 10
Topics: Tree, Segment tree, Union-find
Solved: No attempts yet

Problem

There is a forest with $N$ vertices. The vertices are numbered from $1$ to $N$ , and initially there are no edges. Each vertex $v$ has an integer $X_v$ , and every initial value is $1$ .

Write a program that processes the following queries.

1 a b c: connect vertices $a$ and $b$ with an edge of weight $c$ . This query is given only when the graph remains a forest after it is performed.
2 a b: remove the edge connecting vertices $a$ and $b$ . This query is given only when that edge exists.
3 a: first replace $X_a$ with $1-X_a$ . Then, for the tree containing vertex $a$ , let its vertices be $v_1, v_2, \dots, v_k$ and output the minimum value below.

\min_{1 \le i \le k}\left\{ \sum_{1 \le j \le k} dist(v_i, v_j) \times X_{v_j} \right\}

Here, $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$ . Each of the next $Q$ lines contains one query.

The vertex numbers appearing in queries are encrypted and must be decoded before the query is executed. If the input vertex number is $x$ and the sum of all outputs from type $3$ queries processed so far is $S$ , then the actual vertex number is

(x - 1 + S) \bmod N + 1

Before the first type $3$ query, use $S=0$ . The edge weight $c$ in a type $1$ query is not encrypted.

Output

For each type $3$ query, output the computed value on its own 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$

Examples3

Example 1

Input

Expected output

4
0
0

Example 2

Input

Expected output

Example 3

Input

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

Expected output