题目描述

有$\red {n}$个集合，$\red {m}$个操作，操作分为三种：

$\red {“1~ a~ b” ——}$合并$\red {a,b}$所在集合;

$\red {“2 ~k” ——}$回到输入的第$\red {k}$次操作之后的状态;

$\red {“3 ~a~ b” ——}$询问$\red {a,b}$是否属于同一集合，是则输出$\red {1}$否则输出$\red {0}$。

输入格式

第一行为$\red {n，m}$。

接下来$\red {m}$行描述了每个操作，按照题目描述中所述的格式。

每个操作强制在线，需要对输入的 $\red {a,b,k}$ 进行运算得到真实的 $\red {a,b,k}$ 后再执行操作，运算方法为 $\red {x = x~ xor ~last_{ans}，last_{ans}}$表示上一个询问的答案，其初始值为$\red {0}$。

输出格式

对于每个询问操作，输出一个结果，每个结果占一行。

样例

输入样例

5 6
1 1 2
3 1 2
2 1
3 0 3
2 1
3 1 2

输出样例

1
0
1

提示

$\red {0<n,m≤2\times10^5}$