京畿科学高中（Gyeonggi Science High School）有 $N$ 座建筑物，编号从 $1$ 到 $N$。原本建筑物之间存在道路，但首尔科学高中的学生们喊着“Split the GSHS!”将所有道路都拆除了。

看到这一幕，愤怒的载宇（Jaewoo）让宇贤（Woohyun）重新修建道路。

道路连接两个不同的建筑物，且是双向的。如果可以通过若干条道路从一个建筑物到达另一个建筑物，则称这两个建筑物是连通的。此时，两座建筑物之间的距离定义为连接它们所需经过的道路数量的最小值。

将与某座建筑物连通的所有建筑物中编号最小的建筑物称为该建筑物的“中心建筑物”。此时，与某座建筑物连通的所有建筑物的中心建筑物都是相同的。

载宇向宇贤下达了 $Q$ 次指令。指令分为以下两种类型：

• 1 A B：在建筑物 A 和 B 之间修建一条道路。保证在修建道路之前，不存在既能到达 A 又能到达 B 的建筑物。
• 2 A B：如果建筑物 A 和 B 是连通的，则在连接 A 和 B 的最短路径上（包含 A 和 B），找出距离 A 的中心建筑物最近的建筑物的编号并输出。如果两座建筑物不连通，则输出 0。

你是宇贤，请执行载宇的所有指令。

1. $2 \le N, Q \le 5 \times 10^3$
2. $2 \le N \le 5 \times 10^3$
3. 无额外约束条件

输入格式

第一行给出一个整数 $N$，表示京畿科学高中的建筑物数量。 第二行给出一个整数 $Q$，表示载宇下达的指令数量。 从第三行开始的 $Q$ 行，每行给出一个表示指令类型的整数 $T$ 和两个整数 $X, Y$，中间用空格隔开。此时，对于指令 T A B，其实际参数为：

• $A = X \oplus \texttt{last\_ans}$
• $B = Y \oplus \texttt{last\_ans}$

其中 last\_ans 是上一次执行 2 号指令时输出的结果。如果之前从未执行过 2 号指令，则 last\_ans 为 0。

• $2 \le N \le 10^5$
• $2 \le Q \le 5 \times 10^5$

输出格式

第 $i$ 行输出第 $i$ 个 2 号指令的答案。

样例

输入 1

7 15
1 1 7
2 1 7
1 7 2
2 2 7
1 0 7
2 7 5
1 6 5
2 6 5
2 0 2
1 2 5
2 4 7
2 2 4
1 4 0
2 4 1
2 3 2

输出 1

1
3
3
6
3
1
6
1
6

说明

此处略去样例 1 的图示。