“Dormi’s Fone Service” 现在是 CCOland 唯一的电话服务提供商。CCOland 有 $N$ 座房屋，编号从 $1$ 到 $N$。每条电话线连接两座不同的房屋，且所有存在的电话线构成一个森林。

电话线存在故障，每条电话线仅在一段特定的时间间隔内存在。如果两座房屋在某个时刻之间存在一条由电话线组成的路径，则它们可以在该时刻互相通话。

我们需要处理 $Q$ 个以下形式的查询：

• $1 \ x \ y$：在房屋 $x$ 和 $y$ 之间增加一条电话线。保证房屋 $x$ 和 $y$ 之间此前从未添加过电话线。
• $2 \ x \ y$：移除房屋 $x$ 和 $y$ 之间的电话线。保证房屋 $x$ 和 $y$ 之间当前存在电话线。
• $3 \ t$：计算在当前查询和 $t$ 个查询之前的时间段内，能够互相通话的不同房屋对的数量。更明确地说，令 $G_q$ 为第 $q$ 次查询后 CCOland 的状态，其中 $G_0$ 为任何查询前 CCOland 的状态。如果这是第 $s$ 次查询，则统计在 $G_{s-t}, G_{s-t+1}, \dots, G_s$ 中至少有一个状态下连通的房屋对数量。

此外，部分测试用例可能是加密的。对于加密的测试用例，参数 $x, y$ 或 $t$ 给出的值是真实参数与上一次类型 3 查询答案的按位异或值（如果此前没有类型 3 查询，则参数保持不变）。

输入格式

输入的第一行包含 $E$ ($E \in \{0, 1\}$)。$E = 0$ 表示输入未加密，$E = 1$ 表示输入已加密。

第二行包含两个空格分隔的整数 $N$ 和 $Q$，分别表示 CCOland 中的房屋数量和查询数量。

接下来的 $Q$ 行包含上述查询（根据 $E$ 的值决定是否加密）。

对于第 $q$ 次查询（$1 \le q \le N$），保证（在 $E=1$ 时解密后）对于类型 1 和类型 2 查询有 $1 \le x, y \le N$，对于类型 3 查询有 $0 \le t \le q$。

子任务

输出格式

对于每个类型 3 的查询，在新的一行输出查询的答案。

样例

输入 1

0
4 12
3 0
1 1 2
3 0
1 1 3
3 0
3 5
2 2 1
3 0
3 8
1 1 4
3 0
3 11

输出 1

0
1
3
3
1
3
3
5

说明 1

该测试用例未加密。

对于第 1 次查询，没有不同房屋对可以互相通话。 对于第 3 次查询，只有房屋 1 和 2 可以互相通话。 对于第 5 次查询，$\{(1, 2), (1, 3), (2, 3)\}$ 是可以互相通话的房屋对集合。第 6 次查询结果相同。 对于第 8 次查询，只有房屋 1 和 3 可以互相通话。 对于第 9 次查询，存在某个时间点使得 $\{(1, 2), (1, 3), (2, 3)\}$ 可以互相通话。 对于第 11 次查询，可以互相通话的房屋对集合为 $\{(1, 3), (1, 4), (3, 4)\}$。 对于第 12 次查询，在之前任何时间点可以互相通话的房屋对集合为 $\{(1, 2), (1, 3), (1, 4), (2, 3), (3, 4)\}$。

输入 2

1
4 12
3 0
1 1 2
3 0
1 0 2
3 1
3 6
2 1 2
3 3
3 9
1 2 7
3 3
3 8

输出 2

0
1
3
3
1
3
3
5

说明 2

样例 1 的加密版本。