说明

你正在玩游戏哈利·波特与密室 $2$。你想解锁下一关，即密室。入口门上有 $n$ 个面板，每个面板显示一个由 $m$ 个符号组成的序列。乘积 $nm$ 是偶数。系统通过以下四步过程从一个秘密排列生成这些序列：

• 首先，从一个秘密排列 $[p_1, p_2, \dots, p_{nm/2}]$ 开始；
• 然后，通过将秘密排列与自身连接来重复它，形成数组 $[b_1, b_2, \dots, b_{nm}]$；
• 接着，将这个数组分割成 $n$ 个连续的块，即长度为 $m$ 的不相交子数组；
• 最后，将这些块以任意顺序打乱并分配到各个面板上。

你被给出了系统产生的最终 $n$ 个面板序列。第 $i$ 个面板显示 $[a_{i,1}, a_{i,2}, \dots, a_{i,m}]$。你的任务是恢复一个可能的原始秘密排列 $[p_1, p_2, \dots, p_{nm/2}]$。对于给定的输入，至少存在一个解。如果有多个秘密排列有效，输出其中任意一个。

两个数组 $[x_1, x_2, \dots, x_{k_1}]$ 和 $[y_1, y_2, \dots, y_{k_2}]$ 的连接是长度为 $k_1 + k_2$ 的数组 $[x_1, x_2, \dots, x_{k_1}, y_1, y_2, \dots, y_{k_2}]$。

长度为 $l$ 的一个排列是一个由 $1$ 到 $l$ 的 $l$ 个不同整数以任意顺序组成的数组。例如，$[2,3,1,5,4]$ 是一个排列，但 $[1,2,2]$ 不是排列（$2$ 在数组中出现两次），并且 $[1,3,4]$ 也不是排列（$l = 3$ 但数组中有 $4$）。

输入格式

每个测试点包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 100$）。接下来是对于每个测试用例的描述。

每个测试用例的第一行包含两个整数 $n, m$（$1 \le n \le 70$, $1 \le m \le 70$）—— 面板的数量和每个显示序列的长度。

接下来的 $n$ 行中的第 $i$ 行包含 $m$ 个整数 $a_{i,1}, a_{i,2}, \dots, a_{i,m}$（$1 \le a_{i,j} \le nm/2$），表示第 $i$ 个面板上显示的序列。

注意，所有测试用例中的 $n$ 和 $m$ 之和没有约束。

输出格式

对于每个测试用例，输出一行，包含一个秘密排列 $[p_1, p_2, \dots, p_{nm/2}]$，使得上述过程可以产生 $n$ 个面板序列 $[a_{i,1}, a_{i,2}, \dots, a_{i,m}]$。对于给定的输入，保证至少存在一个解。

5
6 2
1 2
3 4
5 6
5 6
3 4
1 2
5 2
1 3
4 1
2 4
5 2
3 5
5 4
4 1 3 2
6 9 5 10
5 10 4 1
3 2 7 8
7 8 6 9
4 3
3 5 2
1 4 6
1 4 6
3 5 2
1 8
3 1 2 4 3 1 2 4

5 6 3 4 1 2
2 4 1 3 5
3 2 7 8 6 9 5 10 4 1
3 5 2 1 4 6
3 1 2 4

提示

样例解释

在第一个测试用例中，一个有效的秘密排列是 $[p_1, p_2, \dots, p_{nm/2}] = [5, 6, 3, 4, 1, 2]$：

• 数组 $[b_1, b_2, \dots, b_{nm}]$ 是 $[p_1, p_2, \dots, p_{nm/2}] = [5, 6, 3, 4, 1, 2]$ 的两个副本的连接；
• $[b_1, b_2, \dots, b_{nm}]$ 分割成块 $[5, 6]$, $[3, 4]$, $[1, 2]$, $[5, 6]$, $[3, 4]$, $[1, 2]$；
• 打乱后，最终的面板序列 $[a_{i,1}, a_{i,2}, \dots, a_{i,m}]$ 可以与这些块一致。

翻译由 DeepSeek 完成