Busy Beaver 有一个由 $N$ 个整数组成的序列 $a_1, a_2, \dots, a_N$ 和一个由 $M$ 个整数组成的序列 $b_1, b_2, \dots, b_M$。对于每个 $1 \le i \le N$ 和 $1 \le j \le M$，他会计算序列 $a_1, a_2, \dots, a_i$ 与 $b_1, b_2, \dots, b_j$ 之间的编辑距离。两个序列之间的编辑距离定义为：在允许以下三种操作的情况下，将第一个序列转换为第二个序列所需的最少操作次数：

• 插入：可以在序列的任意位置插入任意整数。序列的其余部分保持不变。例如，通过一次操作，序列 $1, 2, 3, 4$ 可以变成 $1, 2, 5, 3, 4$。
• 删除：可以删除序列中存在的任意整数。序列的其余部分保持不变。例如，通过一次操作，序列 $1, 2, 3, 4$ 可以变成 $1, 2, 4$。
• 替换：序列中存在的任意整数都可以被另一个整数替换。序列的其余部分保持不变。例如，通过一次操作，序列 $1, 2, 3, 4$ 可以变成 $1, 2, 5, 4$。

由于存储所有这些值会占用太多空间，Busy Beaver 只存储了每个编辑距离的最低有效位（least significant bit）作为 $d_{i,j}$（如果为偶数则为 $0$，如果为奇数则为 $1$）。

不幸的是，Busy Beaver 丢失了原始序列，现在只知道每个 $i$ 和 $j$ 对应的 $d_{i,j}$ 值。请帮助他找到任意一对序列 $a_1, a_2, \dots, a_N$ 和 $b_1, b_2, \dots, b_M$，使得它们能够产生相同的 $d_{i,j}$ 值。如果不存在任何原始序列能够产生这样的 $d_{i,j}$，则应报告此情况。

输入格式

第一行包含一个整数 $T$（$1 \le T \le 2 \cdot 10^3$）—— 测试用例的数量。

每个测试用例的第一行包含两个整数 $N$ 和 $M$（$1 \le N, M \le 2 \cdot 10^3$）。

接下来的 $N$ 行中，第 $i$ 行包含 $M$ 个整数 $d_{i,1}, d_{i,2}, \dots, d_{i,M}$（$0 \le d_{i,j} \le 1$）。

所有测试用例的 $N$ 之和不超过 $2 \cdot 10^3$。

所有测试用例的 $M$ 之和不超过 $2 \cdot 10^3$。

输出格式

对于每个测试用例，在第一行输出一个由 $N$ 个整数组成的序列 $a_1, a_2, \dots, a_N$（$0 \le a_i \le 10^9$），在第二行输出一个由 $M$ 个整数组成的序列 $b_1, b_2, \dots, b_M$（$0 \le b_i \le 10^9$），使得所有 $d_{i,j}$ 与 $a_1, a_2, \dots, a_i$ 和 $b_1, b_2, \dots, b_j$ 之间的编辑距离具有相同的奇偶性。

如果不存在这样的序列，则在单行中输出 -1。

可以证明，如果存在任何满足要求的序列 $a_1, a_2, \dots, a_N$ 和 $b_1, b_2, \dots, b_M$，那么也必然存在满足 $0 \le a_i \le 10^9$ 且 $0 \le b_i \le 10^9$ 的序列。

样例

输入样例 1

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

输出样例 1

0 1 2 3 3
3 3 1
-1

说明

在第一个测试用例中，可以验证 $[0, 1, 2, 3, 3]$ 和 $[3, 3, 1]$ 是可行的。例如，$[0, 1, 2, 3]$ 和 $[3, 3]$ 之间的编辑距离为 $3$，因为可以通过以下操作完成转换：

1. 删除 $[0, 1, 2, 3]$ 的第一个元素，得到 $[1, 2, 3]$
2. 删除 $[1, 2, 3]$ 的第一个元素，得到 $[2, 3]$
3. 将 $[2, 3]$ 的第一个元素替换，得到 $[3, 3]$

$3$ 的最低有效位是 $1$，这与输入相符。

在第二个测试用例中，可以证明不存在任何合法的序列。