#1460. [yLOI2022] 枕万梦

[yLOI2022] 枕万梦

题目描述

天亮了,扶苏不敌困意,早早地进入了梦乡。在失去引力的梦里,扶苏遇到了好多串漂浮着的数列,它们的长度都相等,而且都是美妙的等比数列!出于本能,扶苏想要把这些数列按照字典序排序,可是在梦里扶苏失去了思考的能力,请你来帮帮她!

具体地,有 nn 个编号从 11 到 nn 的数列 a1,a2,…ana_1, a_2, \dots a_n,每个数列的长度均为 m+1m + 1。第 ii 个数列 aia_i 满足递推式 ai,j=ai,j−1×ia_{i,j} = a_{i,j - 1} \times i,其中 1≤j≤m1 \leq j \leq m。而扶苏会告诉你每个序列的首项 ai,0a_{i,0},你需要帮助她把这些数列按字典序排序。

输入格式

输入的第一行是两个整数,依次表示 nn 和 mm。
接下来 nn 行,每行一个整数,第 ii 行的整数表示数列 aia_i 的首项 ai,0a_{i,0}。

输出格式

输出一行 nn 个整数,第 ii 个整数表示字典序第 ii 小的数列的编号。

样例

2 2
1
2
1 2
2 3
1
-1
2 1
2 2
1
1
1 2
见附加文件中的 B4.in
见附加文件中的 B4.ans

题目来源:洛谷 P9472