夏天已经变得漫长而无聊，为了消遣，你开始翻阅一些近期的论文。你偶然发现了一个有趣的问题：考虑一个由 $n$ 个 $\{1, 2, \dots, m\}$ 上的排列 $X^1, \dots, X^n$ 组成的列表。换句话说，每个 $X^i$ 都是一个大小为 $m$ 的向量 $X^i_1, \dots, X^i_m$，其中 $1$ 到 $m$ 的所有数字各出现恰好一次。这篇论文讨论的是重新排列给定的排列，使得新的顺序（记为 $Y^1, \dots, Y^n$）是“单交叉”（single-crossing）的。

如果对于任意三个下标 $1 \le i < j < k \le n$ 以及任意两个不同的值 $1 \le a, b \le m$，只要 $a$ 在 $Y^i$ 和 $Y^k$ 中都出现在 $b$ 之前，那么 $a$ 在 $Y^j$ 中也出现在 $b$ 之前，我们就称排列序列 $Y^1, \dots, Y^n$ 是单交叉的。

更直观地说：我们称 $Y^1, \dots, Y^n$ 是单交叉的，当且仅当任意两个元素 $a$ 和 $b$ 改变其相对顺序的次数最多为一次。

你已经找不到那篇论文了，但你非常想实现它所提出的问题的解法。因此，给定 $t$ 组测试数据，请为每组数据判断是否存在一种重新排列这些排列的方法使其成为单交叉序列，如果存在，输出其中一种可能的方案。

输入格式

第一行包含一个整数 $t$ ($1 \le t \le 5$)，表示测试数据的组数。

每组测试数据描述如下：第一行包含两个整数 $n$ 和 $m$ ($1 \le n \le 10^5$; $1 \le n \cdot m \le 10^6$)。接下来的 $n$ 行，每行包含 $m$ 个整数，表示排列 $X^1, \dots, X^n$。

输出格式

对于每组测试数据，输出一行。如果无法通过重新排列使得序列变为单交叉，输出 -1。否则，输出一个包含 $n$ 个空格分隔整数的排列 $p$，表示原始排列重新排列后的顺序。

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

样例

输入 1

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

输出 1

2 3 1 5 4
-1

说明 1

对于第一组测试数据，排序后的顺序为 2 3 1 5 4： 1 2 3 4 2 1 3 4 2 3 1 4 3 2 4 1 4 3 2 1