最初，我们有 $k$ 个 $1$ 到 $n$ 的排列。我们通过将每个排列及其逆排列分别写成一行，创建了一个 $2k \times n$ 的矩阵。然而，我们忘记了这些排列，且有人打乱了每一列的顺序。给定这个矩阵，你能确定我们最初可能使用的任意一组排列吗？

输入格式

第一行包含两个整数 $n$ 和 $k$ ($1 \le n \le 4 \cdot 10^4$, $1 \le k \le 7$)。

接下来的 $2k$ 行中，第 $i$ 行包含 $n$ 个整数 $a_{ij}$，表示矩阵的第 $i$ 行 ($1 \le a_{ij} \le n$)。

保证该矩阵一定是由上述过程生成的。

输出格式

输出 $k$ 行。每一行应包含一个 $1$ 到 $n$ 的排列。在将这些排列及其逆排列写成 $2k \times n$ 的矩阵后，必须能够通过重新排列每一列中的值来得到输入的矩阵。

如果存在多种解，输出其中任意一个即可。

样例

样例输入 1

3 1
1 2 3
1 2 3

样例输出 1

1 2 3

样例输入 2

4 2
1 1 3 4
4 3 2 1
2 4 2 4
1 3 3 2

样例输出 2

1 3 2 4
4 1 3 2