#P18170. Piggy Sort
Piggy Sort
Piggy Sort
Putata 和 Budada 提出了一种排序方法:为每个待排序的非负实数找一只速度恰为这个数的小猪,让所有小猪在数轴上同时开始奔跑。经过足够长的时间,小猪的位置顺序便体现了速度顺序。
共有 只小猪。第 只小猪的初始位置为 ,速度为非负实数 。初始位置两两不同;速度可以相同,也可以为 0。经过 秒,它的位置为 。
他们拍摄了 张照片,其中 。所有照片的拍摄时刻互不相同。第一张在时刻 0 拍摄,其他照片的拍摄时刻和先后顺序均无法辨认。
每张照片只能辨认小猪的位置,无法辨认小猪的身份。第 张照片中,从左到右的位置为 。小猪可能在拍摄时重合,因此第一张以外的照片中允许出现相同位置。
请给第一张照片中从左到右的每只小猪确定速度排名,输出排列 。速度更小的小猪排名更小;速度相同的小猪中,初始位置更小的排名更小。形式化地,要求
$$r_i<r_j\iff(v_i<v_j)\lor(v_i=v_j\land x_{1,i}<x_{1,j}).$$输入格式
第一行整数 (),表示实验组数。
每组实验第一行两个整数 ()。
接下来 行,每行 个整数,表示一张照片上的小猪位置,满足
$$-10^7\le x_{i,j}\le10^7,\qquad x_{i,j}\le x_{i,j+1}.$$保证第一张照片的位置两两不同。输入描述的是上述真实实验。
保证全部实验的 之和不超过 500。
输出格式
每组实验输出一行 个整数,表示 。它们必须构成 的一个排列。若存在多种合法答案,输出任意一种。
样例
输入:
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