Tree and Queries 20

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$.

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.

For each type $3$ query, output the computed value on its own line, in the order the queries are given.

• $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$