为您提供一个包含 $$$n$$$ 行和 $$$m$$$ 列的网格,其中每个单元格上都写有一个正整数。如果每一行中的数字序列都按非递减顺序排序,那么我们称网格为好的网格。这意味着,对于每个 $$$1 \le i \le n$$$ 和 $$$2 \le j \le m$$$,以下内容成立:$$$a_{i,j} \ge a_{i, j-1}$$$。
您必须执行以下操作一次:选择索引为 $$$i$$$ 和 $$$j$$$ (不一定不同)的两列,$$$1 \le i, j \le m$$$,然后交换它们。
系统会要求您确定交换后网格是否可以恢复正常,如果可以,则找到需要交换的列。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 100$$$)。测试用例的描述如下。
每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n, m \le 2 \cdot 10^5$$$) - 分别是行数和列数。
接下来的 $$$n$$$ 行包含 $$$m$$$ 整数,$$$i$$$ 行的第 $$$j$$$ 元素为 $$$a_{i,j}$$$ ($$$1 \le a_{i,j} \le 10^9$$$) — 写入第 $$$j$$$ 单元格的数字$$$i$$$第行。
保证所有测试用例的 $$$n \cdot m$$$ 之和不超过 $$$2 \cdot 10^5$$$。
输出
如果交换后无法得到好的网格,则输出$$$-1$$$。
在另一种情况下,输出 $$$2$$$ 整数 - 应该交换以获得良好网格的列的索引。
如果有多个解决方案,请打印其中一个。
示例
输入 #1
5 2 3 1 2 3 1 1 1 2 2 4 1 2 3 2 2 2 1 1 1 2 3 6 2 1 5 4 3 2 1 1 2
输出 #1
1 1 -1 1 2 1 3 1 1
注意
在第一个测试用例中,网格最初是好的,因此我们可以,例如,将第一列与其自身交换。
在第二个测试用例中,不可能使网格良好。
在第三个测试用例中,需要交换第一列和第二列,然后网格就变好了。