Putata 和 Budada 提出了一种新的算法：小猪排序（Piggy Sort）。该算法可以通过以下过程轻松地对 $n$ 个实数进行排序：

• 假设需要排序的序列为 $v_1, v_2, \dots, v_n$，它们是 $n$ 个非负实数。
• Putata 和 Budada 精心挑选了 $n$ 只来自 Pigetown 的小猪，这些小猪的速度恰好为 $v_1, v_2, \dots, v_n$。Pigetown 可以用坐标轴来描述。第 $i$ 只小猪最初位于坐标 $x_i$。小猪的初始坐标两两不同。
• 所有小猪同时开始奔跑。$t$ 秒后，第 $i$ 只小猪位于坐标 $x_i + v_i \cdot t$。注意速度可能为零，这意味着小猪根本不动。
• 经过相当长的时间后，坐标轴上小猪的顺序即为序列 $v_1, v_2, \dots, v_n$ 的（已排序）顺序。

Putata 和 Budada 进行了一项实验来验证该算法的正确性。然而，时间就是金钱，漫长的等待时间是不切实际的。作为替代方案，他们拍摄了 $m$ 张小猪的照片。为了确保有足够的实验数据，他们保证照片数量多于数组中的元素数量，即 $m > n$。

不幸的是，照片中的大部分信息已损坏。他们只能从照片中获得以下信息：

• 第一张照片是在时间 $0$ 拍摄的，而其他照片拍摄的时间无法区分。这些照片是在不同的时间拍摄的。
• 第 $i$ 张照片中小猪的坐标为 $x_{i,1}, x_{i,2}, \dots, x_{i,n}$，但无法区分具体哪只小猪是哪一只。

请帮助 Putata 和 Budada 找出实验结果。你需要找到一个序列 $r_1, r_2, \dots, r_n$，它是第一张照片中坐标第 $i$ 小的小猪的速度排名。你需要保证 $r_i < r_j$ 当且仅当 $(v_i < v_j) \lor ((v_i = v_j) \land (x_{1,i} < x_{1,j}))$，且 $r_1, r_2, \dots, r_n$ 是 $1, 2, \dots, n$ 的一个排列。

输入格式

输入包含多个测试用例。第一行包含一个整数 $t$ ($1 \le t \le 250$)，表示测试用例的数量。

对于每个测试用例，第一行包含两个整数 $n, m$ ($1 \le n < m \le 500$)，分别表示数组的长度和照片的数量。

接下来的 $m$ 行中，第 $i$ 行包含 $n$ 个整数，其中第 $j$ 个整数表示 $x_{i,j}$ ($-10^7 \le x_{i,j} \le 10^7, x_{i,j} \le x_{i,j+1}$)，即第 $i$ 张照片中小猪的位置。保证 $x_{1,u} = x_{1,v}$ 当且仅当 $u = v$。

保证所有测试用例的 $m$ 之和不超过 $500$。

输出格式

对于每个测试用例，输出一行 $n$ 个整数，表示 $r_1, r_2, \dots, r_n$。

你需要保证 $r_1, r_2, \dots, r_n$ 是 $1, 2, \dots, n$ 的一个排列。如果存在多个答案，输出任意一个即可。

样例

输入 1

3
2 4
1 2
3 4
5 6
7 8
1 2
1
1
3 4
1 2 3
6 9 9
10 15 17
12 18 21

输出 1

1 2
1
3 1 2