Problem Background

As the miko of Yae Village, Sakura bears the responsibility of guarding the village. The village is under threat from the Collapse, and Yae Sakura, engage!

Problem Description

The ancient village of Yae has $n$ houses. Initially, there are no roads between any of the houses. As the village develops, bidirectional roads connecting two houses gradually appear.

The villagers originally lived a carefree and happy life until they faced the Collapse. Slowly, a house may be attacked by a beast of the Collapse, each beast possessing a certain amount of Collapse energy, and each house may contain multiple beasts.

Sakura arrives and accepts exorcism commissions, each commission involving the expulsion of Collapse beasts from one house to another. Sakura can only travel on existing roads. Since there may be multiple paths, the clever Sakura will only choose certain points that are essential on all paths, i.e., the critical points. Each commission will involve exorcising at all critical points between the two houses.

Input Format

The first line contains two integers: $n, m$, representing the number of houses and the number of events, respectively.

The next $m$ lines each contain three positive integers: $opt, x, y$.

When $opt = 1$, it indicates that a bidirectional road is built between house $x$ and house $y$ (guaranteed no duplicate edges, but self-loops are not guaranteed; ignore them if present).

When $opt = 2$, it indicates that a Collapse beast with energy $y$ has arrived at house $x$.

When $opt = 3$, it indicates that Sakura has completed an exorcism commission from house $x$ to house $y$ (not guaranteed to be connected; output $0$ if not connected).

The input is forcefully online: Let the last answer for $opt = 3$ be $\text{lastans}$, initially $0$. The actual $x, y$ are decoded using the function:

inline const void decode(int &x)
{
    x ^= lastans % n;
    if (x > n) x %= n;
    if (!x) x = 1;
}

Output Format

For each $opt = 3$ event, output a single number on a line representing the amount of Collapse energy cleared by Sakura. The answer is guaranteed to be within $[0, 2^{63})$.

Sample Input and Output

Sample Input #1

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

Sample Output #1

3
0

Sample Input #2

4 8
2 1 629
3 3 1
2 4 923
1 4 2
2 4 542
2 1 918
1 2 3
3 4 3

Sample Output #2

0
5

Notes

Sample 1 Explanation

The fourth event adds 1 point of Collapse energy to house 1.

The fifth event adds 2 more points of Collapse energy to house 1, making its total 3.

The sixth event clearly has an answer of 3, updating $\text{lastans} = 3$.

The seventh event has the actual $x = 1$, $y = 3$. Since the sixth event already exorcised at house 1, there is no Collapse energy left.

Subtask #1 (20 points):

$1 \leq n, m \leq 100000$.

Subtask #2 (70 points):

$1 \leq n, m \leq 200000$.

Subtask #3 (10 points):

$1 \leq n, m \leq 500000$.

All test cases have a time limit of 1.5 seconds and a memory limit of 125 MiB.

见题面 Input 部分

见题面 Output 部分