Background

As the miko of Yae Village, Sakura takes on the responsibility of guarding the village. The village is threatened by the Honkai. Yae Sakura, sortie!

Problem Description

There are $n$ houses in the ancient Yae Village. At the beginning, there are no roads between any houses. As the village develops, undirected roads connecting two houses will gradually be built.

The villagers originally lived a carefree and happy life, until they went against civilization—the Honkai came. Gradually, some house may be attacked by Honkai beasts. Each Honkai beast has a certain amount of Honkai energy, and there may be multiple Honkai beasts in a single house.

Sakura has arrived. She accepts exorcism commissions. Each commission is to drive out the Honkai beasts from one house to another house. Sakura can only walk along existing roads. Since there may be many different paths, the smart Sakura will only choose some nodes that are passed by on all possible paths between them, i.e. mandatory nodes. For each commission, Sakura exorcises on all mandatory nodes on all paths between the two given houses.

Input Format

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

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

When $opt=1$, it means an undirected road is built between house $x$ and house $y$ (it is guaranteed that there are no multiple edges, but self-loops are not forbidden; if there is one, ignore it).

When $opt=2$, it means a Honkai beast with Honkai energy $y$ comes to house $x$.

When $opt=3$, it means Sakura completes an exorcism commission from $x$ to $y$ (it is not guaranteed that $x$ and $y$ are connected; if they are not connected, just output $0$).

Forced online: let the answer of the last type $3$ event be $\text{lastans}$, with initial value $0$. The actual $x,y$ are decoded by the following function:

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

Output Format

For each type $3$ event, output one number per line representing the amount of Honkai energy cleared by Sakura. The answer is guaranteed to be in $[0,2^{63})$.

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

3
0

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

0
5

Hint

[Sample $1$ Explanation]

The 4th event makes house $1$ have $1$ point of Honkai energy.

The 5th event increases the Honkai energy of house $1$ by $2$, so its Honkai energy becomes $3$.

For the 6th event, the answer is clearly $3$, and update $\text{lastans}=3$.

In the 7th event, the real $x=1$, $y=3$. Since the 6th event has already exorcised at $1$, there is no Honkai energy.

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

For all test points, the time limit is $1.5 \text s$, and the memory limit is $125 \text{MiB}$.

Problem Provider: $\color{red}{zhengrunzhe}$

Translated by ChatGPT 5