#P18170. Piggy Sort

Piggy Sort

Piggy Sort

Putata 和 Budada 提出了一种排序方法:为每个待排序的非负实数找一只速度恰为这个数的小猪,让所有小猪在数轴上同时开始奔跑。经过足够长的时间,小猪的位置顺序便体现了速度顺序。

共有 nn 只小猪。第 ii 只小猪的初始位置为 xix_i,速度为非负实数 viv_i。初始位置两两不同;速度可以相同,也可以为 0。经过 tt 秒,它的位置为 xi+vitx_i+v_it。

他们拍摄了 mm 张照片,其中 m>nm>n。所有照片的拍摄时刻互不相同。第一张在时刻 0 拍摄,其他照片的拍摄时刻和先后顺序均无法辨认。

每张照片只能辨认小猪的位置,无法辨认小猪的身份。第 ii 张照片中,从左到右的位置为 xi,1,…,xi,nx_{i,1},\ldots,x_{i,n}。小猪可能在拍摄时重合,因此第一张以外的照片中允许出现相同位置。

请给第一张照片中从左到右的每只小猪确定速度排名,输出排列 r1,…,rnr_1,\ldots,r_n。速度更小的小猪排名更小;速度相同的小猪中,初始位置更小的排名更小。形式化地,要求

$$r_i<r_j\iff(v_i<v_j)\lor(v_i=v_j\land x_{1,i}<x_{1,j}).$$

输入格式

第一行整数 tt(1≤t≤2501\le t\le250),表示实验组数。

每组实验第一行两个整数 n,mn,m(1≤n<m≤5001\le n<m\le500)。

接下来 mm 行,每行 nn 个整数,表示一张照片上的小猪位置,满足

$$-10^7\le x_{i,j}\le10^7,\qquad x_{i,j}\le x_{i,j+1}.$$

保证第一张照片的位置两两不同。输入描述的是上述真实实验。

保证全部实验的 mm 之和不超过 500。

输出格式

每组实验输出一行 nn 个整数,表示 r1,…,rnr_1,\ldots,r_n。它们必须构成 1,…,n1,\ldots,n 的一个排列。若存在多种合法答案,输出任意一种。

样例

输入:

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