Mirko 收到了一项有趣的家庭作业：设计他自己的微型处理器（Mirkoprocessor）。该处理器有 $N$ 个寄存器，索引从 $1$ 到 $N$，每个寄存器存储一个无符号 32 位整数，采用通常的二进制格式（可能的值范围为 $0$ 到 $2^{32} - 1$）。

该处理器能够执行以下类型的指令：

Mirko 已经构建了该处理器的模型，但随后才意识到他忘记了添加读取寄存器内容的指令。现在，他唯一的选择是执行大量的 1 类和 2 类指令，并从结果中推断出寄存器的内容。在执行了一系列指令后，他请求你帮助他推导出与得到的结果相一致的初始寄存器内容。

如果初始寄存器状态组合存在多种可能性，请找出字典序最小的一种。（如果两个组合在前 $K - 1$ 个寄存器中的值相等，而在第 $K$ 个寄存器中的值不同，则在第 $K$ 个寄存器中值较小的组合是字典序较小的组合。）

输入格式

输入的第一行包含两个正整数：$N$（$2 \le N \le 100\,000$），表示寄存器的数量；$E$（$1 \le E \le 100\,000$），表示已执行的指令数量。

接下来的输入行按 Mirkoprocessor 执行的顺序描述了这些指令，格式如上表所示，每行一条指令。所有指令都是合法的（满足以下条件：$1 \le K, L \le N$，$0 \le M < 32$）。每条 2 类指令后面都会紧跟另一行，其中包含一个介于 $0$ 和 $2^{32} - 1$ 之间（含）的整数——该操作在十进制下的结果（按位异或值）。

输出格式

输出的第一行也是唯一一行必须包含所需的 $N$ 个寄存器值，用空格隔开。

如果不存在与输入相一致的初始值组合，则仅输出数字 -1，以通知 Mirko 他的处理器存在 bug。

子任务

在占总分 64 分的测试数据中，数字 $N$ 和 $E$ 将小于 $1000$。

样例

输入样例 1

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

输出样例 1

0 1 2

输入样例 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

输出样例 2

5 0 14 3

输入样例 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

输出样例 3

15 6 7 12 5