题目描述

夏天已经漫长而无聊了，为了打发时间，你开始阅读一些最近的论文。你偶然看到一个有趣的问题：考虑 $n$ 个 $\{1,2,\ldots,m\}$ 上的排列 $X^1,X^2,\ldots,X^n$。换句话说，每个 $X^i$ 都是一个长度为 $m$ 的向量 $X^i_1,X^i_2,\ldots,X^i_m$，其中 $1$ 到 $m$ 的每个数恰好出现一次。

论文研究的是：是否可以重新排列这些给定排列的顺序，使得重新排列后的序列 $Y^1,Y^2,\ldots,Y^n$ 是 single-crossing 的。

称一个排列序列 $Y^1,Y^2,\ldots,Y^n$ 是 single-crossing 的，当且仅当对于任意三个下标

以及任意两个不同的值

如果在 $Y^i$ 和 $Y^k$ 中，$a$ 都出现在 $b$ 的前面，那么在 $Y^j$ 中，$a$ 也必须出现在 $b$ 的前面。

更直观地说，序列 $Y^1,Y^2,\ldots,Y^n$ 是 single-crossing 的，当且仅当任意两个元素 $a$ 和 $b$ 的相对顺序在整个序列中至多改变一次。

你已经找不到那篇论文了，但你仍然很想实现论文中提出的问题。给定 $t$ 组测试数据，请判断每组数据是否存在一种重新排列这些排列的方式，使得得到的序列是 single-crossing 的；如果存在，请输出任意一种方案。

输入格式

第一行包含一个整数 $t$，表示测试数据组数。

接下来依次描述 $t$ 组测试数据。

对于每组测试数据，第一行包含两个整数 $n,m$。

接下来 $n$ 行，每行包含 $m$ 个整数，表示排列 $X^1,X^2,\ldots,X^n$。

输出格式

对于每组测试数据，输出一行。

如果无法重新排列这些排列，使得序列变为 single-crossing，则输出 -1。

否则，输出一个长度为 $n$ 的排列 $p$，包含 $n$ 个用空格分隔的整数，表示应按如下顺序重排原来的排列：

如果存在多种合法方案，输出任意一种即可。

数据范围

对于所有测试数据，满足：

并且对于每组测试数据，满足：

每个输入的 $X^i$ 都是 $\{1,2,\ldots,m\}$ 上的一个排列。

样例

样例输入

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

样例输出

2 3 1 5 4
-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

该序列是 single-crossing 的。