[DBOI2019] 巫女的职责

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

八重古村有 $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$ 用函数解码： ```cpp 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}$](https://www.luogu.org/space/show?uid=14374)