题目描述

这是一道假的模板题

我们有一个数组 $A$，初始时只有 $A[0]$ 是空序列。对于第 $i$ 个操作：

• 1 ver t 表示将 $A[ver]$ 复制到 $A[i]$，并在 $A[ver]$ 结尾插入元素 $t$
• 2 ver 表示将 $A[ver]$ 复制到 $A[i]$，并删除 $A[ver]$ 开头的元素（保证 $A[i]$ 非空）

此外，你需要维护一个变量 $hash$，其初始值为 $0$，每次执行完第二类操作时，将 $hash$ 变为 $(31 \times hash + x) \bmod 2^{32}$，其中 $x$ 是被删除的元素。

$hash$ 是你的最终输出的答案。

此外，输入数据有可能加密，取决于输入参数 $ty$ 的值。如果 $ty = 0$，那么数据没有加密；否则，$ty=1$，那么读入 $ver$ 和 $t$ 的值，其真实值应与当前的 $hash$ 取按位异或，也就是说真实值应为 $ver \oplus hash$ 和（对于第一类操作） $t \oplus hash$。

输入格式

第一行有两个整数，$T$ 和 $ty$，表示有多少个操作，和数据是否加密。

之后的 $T$ 行，每一行表示一个如上所述的操作。

输出格式

只有一行，表示执行完所有操作之后，$hash$ 的值。

样例

样例输入一

9 0
1 0 1
1 1 2
2 1
2 2
2 2
2 4
1 4 5
2 7
2 8

样例输出一

29584452

样例解释一

样例输入二

9 1
1 0 1
1 1 2
2 1
2 3
2 34
2 997
1 30789 30788
2 30790
2 954345

样例输入二

29584452

样例解释二

解密后，与样例一相同

数据范围与提示

对于所有操作，保证操作合法，即格式正确，不会在空的版本上进行操作 $2$，$ver \geq 0$ 且 $ver$ 小于当前操作编号。

对于第一类操作，$0 \leq t \lt 10000000$

请使用无符号整数进行输入输出！变量应使用 unsigned 类型，printf 和 scanf 应使用 %u 格式。

如果你使用冲击满分的算法，但是使用 scanf，你的程序很可能将花费超过 $80\%$ 的运行时间在输入数据。所以请务必使用读入优化！可以参考附加文件中 bqsg 提供的 read.cpp 实现的 A + B Problem 的程序。