题目背景
岁月冥冥之中 星移物换 将韶华歌颂
人潮冥冥之中 一眼望穿 日月去无踪
你我冥冥之中 心有灵犀 何止几万梦
忘情在这久违的重逢
天地冥冥之中 云烟奔涌 摩肩又接踵
万籁冥冥之中 不肯缄默 盛大到无穷
你我冥冥之中 对坐天涯 灵犀才一动
就相遇在咫尺的时空
银临《枕万梦》
题目描述
天亮了,扶苏不敌困意,早早地进入了梦乡。在失去引力的梦里,扶苏遇到了好多串漂浮着的数列,它们的长度都相等,而且都是美妙的等比数列!出于本能,扶苏想要把这些数列按照字典序排序,可是在梦里扶苏失去了思考的能力,请你来帮帮她!
具体地,有 n 个编号从 1 到 n 的数列 a1,a2,…an,每个数列的长度均为 m+1。第 i 个数列 ai 满足递推式 ai,j=ai,j−1×i,其中 1≤j≤m。而扶苏会告诉你每个序列的首项 ai,0,你需要帮助她把这些数列按字典序排序。
输入格式
输入的第一行是两个整数,依次表示 n 和 m。
接下来 n 行,每行一个整数,第 i 行的整数表示数列 ai 的首项 ai,0。
输出格式
输出一行 n 个整数,第 i 个整数表示字典序第 i 小的数列的编号。
2 2
1
2
1 2
2 3
1
-1
2 1
2 2
1
1
1 2
见附加文件中的 B4.in
见附加文件中的 B4.ans
提示
样例 1 解释
共有两个数列,每个数列的长度均为 2+1=3。
对第一个数列 a1:
- 已知其首项 a1,0=1。
- 根据 ai,j=ai,j−1×i,取 i=1,j=1 可以得到 a1,1=a1,0×1=1。
- 根据 ai,j=ai,j−1×i,取 i=1,j=2 可以得到 a1,2=a1,1×1=1。
所以数列 a1 是 1,1,1。
对第二个数列 a2:
- 已知其首项 a2,0=2。
- 根据 ai,j=ai,j−1×i,取 i=2,j=1 可以得到 a2,1=a2,0×2=2×2=4。
- 根据 ai,j=ai,j−1×i,取 i=2,j=2 可以得到 a2,2=a2,1×2=4×2=8。
所以数列 a2 是 2,4,8。
比较字典序可得数列 a1 是字典序最小的数列。所以输出 1。
样例 2 解释
数列 a1 为 1,1,1,1,数列 a2 为 −1,−2,−4,−8。
数据规模与约定
本题共 10 个测试点,各测试点信息如下表:
特殊约定 A:保证 ai,0 均相等。
特殊约定 B:保证 ai,0 互不相等。
对全部的测试点,保证 1≤n≤105,1≤m≤109,1≤∣ai,0∣≤109。
提示
对两个数列 ai,aj,按如下方式比较其字典序:
找到最小的满足 ai,p=aj,p 的下标 p,比较 ai,p 和 aj,p 的大小:
- 如果 ai,p<aj,p,则称 ai 的字典序比 aj 的小。
- 如果 ai,p>aj,p,则称 ai 的字典序比 aj 的大。
可以证明,在本题的限制下,这样的 p 一定存在。