题目背景

作为八重村的巫女，樱承担着守卫村庄的责任，村子里受到了崩坏的威胁，八重樱，出击！

题目描述

八重古村有 $n$ 座房屋，一开始所有的房子之间都没有路，随着古村的发展，慢慢会出现连接两栋房屋的双向道路。

村民们原本过着无忧无虑的幸福生活，直到与文明作对——崩坏来了，慢慢地，某栋房屋也许会在遭受崩坏兽的侵袭，每只崩坏兽都有着一定的崩坏能，每户人家也许会存在着多只崩坏兽。

樱来了，她接受了驱魔委托，每个委托都是从驱逐某个房子到另一个房子的崩坏兽，樱只能走已有的路，由于这样的路径也许有很多条，聪明的樱只会选择在它们所有路径中都会走过的某些点，即必经点，每次委托樱会在两点间的所有必经点驱魔。

输入格式

第一行两个整数：$n,m$ 表示房屋数和事件数

接下来 $m$ 行，每行三个正整数：$opt,x,y$

$opt=1$时，表示房子 $x$ 和房子 $y$ 间修了一条双向道路(保证没有重边，但不保证没有自环，如有请忽略。)

$opt=2$ 时，表示房子 $x$ 来了一只崩坏能为 $y$ 的崩坏兽

$opt=3$ 时，表示樱完成了一次从 $x$ 到 $y$ 的驱魔委托(不保证 $x$ 与 $y$ 连通，不连通输出 $0$ 即可)

强制在线：记上次$3$的答案为 $\text{lastans}$，初值为 $0$，实际上的$x,y$ 用函数解码：

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

输出格式

对于每个 $3$ 事件，输出一行一个数表示樱清除的崩坏能的值，答案保证在 $[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

提示

【样例 $1$ 说明】

第四个事件使 $1$ 号房屋有 $1$ 点的崩坏能。

第五个事件使 $1$ 号房屋增加了 $2$ 点的崩坏能，此时其崩坏能值为 $3$。

第六个事件显然答案为 $3$，更新 $\text{lastans}=3$ 。

第七个事件真实的 $x=1$，$y=3$，由于第六个事件已经在 $1$ 驱魔，所以没有崩坏能。

$Subtask$ #$1$（$20$ 分）：

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

$Subtask$ #$2$（$70$ 分）：

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

$Subtask$ #$3$（$10$ 分）：

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

所有测试点的时间限制统一为 $1.5 \text s$，内存限制统一为 $125 \text{MiB}$。

题目提供者：$\color{red}{zhengrunzhe}$