题目描述

Mirko 收到了一份有趣的作业：设计一个他自己的小处理器。这个处理器有编号从 $1$ 到 $n$ 的 $n$ 个寄存器，每一个寄存器上面以二进制形式保存一个无符号的 $32$ 位整数（可能的数值在 $[0,2^{32}-1]$ 之间）。

除此以外，这个处理器还要求完成以下两种操作：

• 1 k m： 将寄存器 $k$ 上的数的二进制表示的后 $m$ 位整体提到最前面，然后将得到的新数字重新写入寄存器 $k$。例如：

$$\begin{aligned}&00000000000000000010001111111011\\\xrightarrow{m=10}&11111110110000000000000000001000\end{aligned} $$

• 2 k l：计算寄存器 $k$ 上的数和寄存器 $l$ 上的数异或的结果并将结果输出到系统上。例如：

$$\begin{aligned}&00000000000000000000001111000111\\\underline\text{XOR }&\underline{00000000000001111100000000000111}\\\text{= }&00000000000001111100001111000000\end{aligned} $$

Mirko 直到他建立了这个处理器模型才意识到他忘记实现一个读取寄存器内容的操作。因此，他现在唯一能做的就是大量执行操作 $1$ 和操作 $2$，并从结果中推断寄存器内容。在执行了一系列命令之后，他要求您帮助他推导出与获得的结果一致的初始寄存器内容的组合。

如果初始寄存器状态组合有多种可能，则你需要求按字典顺序排列的最小值的组合（如果两个组合在前 $k–1$ 个寄存器中具有相等的值，而在寄存器 $k$ 中具有不同的值，则按字典顺序排列的较小组合就是在寄存器 $k$ 中具有较小值的组合）。

输入格式

输入共若干行。

第一行，两个整数 $n,e$，分别表示寄存器总数和操作次数。
接下来若干行用来描述每一个操作。对于一个操作，先输入一行三个整数 $\textit{op},k,l$，分别表示操作类型和该操作类型的两个参数。如果 $op=2$，则接下来应再输入一行一个整数，表示上一行的操作 $2$ 得到的结果，然后再在下一行进入下一个操作的输入。否则下一行直接进入下一个操作的输入。

如果您不能很好地理解输入格式，请参照样例以对这一部分有更好的理解。

输出格式

如果不存在与输入一致的初始寄存器内容组合，则仅输出一行一个整数 $-1$。否则输出一行 $n$ 个整数，第 $i$ 个整数表示一开始第 $i$ 个寄存器上的数。

3 3
2 1 2
1
2 1 3
2
2 2 3
3

0 1 2

4 6
2 4 2
3
2 4 1
6
1 3 1
2 3 1
2
1 2 2
2 2 3
7

5 0 14 3

5 6
2 4 2
10
2 5 3
2
2 2 3
1
2 1 4
3
1 3 1
2 3 4
2147483663

15 6 7 12 5

提示

【数据范围】

对于 $40\%$ 的数据，满足 $n,e\leqslant 1000$。
对于所有数据，$2\leqslant n\leqslant 10^5$，$1\leqslant e\leqslant 10^5$。且满足：

• $op=1$ 时，$1\leqslant k\leqslant n$，$0\leqslant l\leqslant 32$。
• $op=2$ 时，$1\leqslant k,l\leqslant n$。

【题目来源】

本题来源自 COCI 2012-2013 CONTEST 3 T6 PROCESOR，按照原题数据配置，满分 $160$ 分。

由 Eason_AC 翻译整理提供。