#LUOGUP8677. [yLOI2022] 枕万梦

[yLOI2022] 枕万梦

题目背景

岁月冥冥之中 星移物换 将韶华歌颂
人潮冥冥之中 一眼望穿 日月去无踪
你我冥冥之中 心有灵犀 何止几万梦
忘情在这久违的重逢
天地冥冥之中 云烟奔涌 摩肩又接踵
万籁冥冥之中 不肯缄默 盛大到无穷
你我冥冥之中 对坐天涯 灵犀才一动
就相遇在咫尺的时空

银临《枕万梦》

题目描述

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

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

输入格式

输入的第一行是两个整数,依次表示 nnmm
接下来 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

提示

样例 1 解释

共有两个数列,每个数列的长度均为 2+1=32+1=3

对第一个数列 a1a_1

  • 已知其首项 a1,0=1a_{1,0} = 1
  • 根据 ai,j=ai,j1×ia_{i,j} = a_{i,j - 1} \times i,取 i=1,j=1i=1,j = 1 可以得到 a1,1=a1,0×1=1a_{1,1} = a_{1,0} \times 1 = 1
  • 根据 ai,j=ai,j1×ia_{i,j} = a_{i,j - 1} \times i,取 i=1,j=2i=1,j = 2 可以得到 a1,2=a1,1×1=1a_{1,2} = a_{1,1} \times 1= 1

所以数列 a1a_11,1,11,1,1

对第二个数列 a2a_2

  • 已知其首项 a2,0=2a_{2,0} = 2
  • 根据 ai,j=ai,j1×ia_{i,j} = a_{i,j - 1} \times i,取 i=2,j=1i=2,j = 1 可以得到 a2,1=a2,0×2=2×2=4a_{2,1} = a_{2,0} \times 2 = 2 \times 2 = 4
  • 根据 ai,j=ai,j1×ia_{i,j} = a_{i,j - 1} \times i,取 i=2,j=2i=2,j = 2 可以得到 a2,2=a2,1×2=4×2=8a_{2,2} = a_{2,1} \times 2= 4 \times 2 = 8

所以数列 a2a_22,4,82,4,8

比较字典序可得数列 a1a_1 是字典序最小的数列。所以输出 11

样例 2 解释

数列 a1a_11,1,1,11,1,1,1,数列 a2a_21,2,4,8-1, -2,-4,-8

数据规模与约定

本题共 1010 个测试点,各测试点信息如下表:

特殊约定 A:保证 ai,0a_{i,0} 均相等。
特殊约定 B:保证 ai,0a_{i,0} 互不相等。

对全部的测试点,保证 1n1051 \leq n \leq 10^51m1091 \leq m \leq 10^91ai,01091 \leq |a_{i,0}| \leq 10^9

提示

对两个数列 ai,aja_i, a_j,按如下方式比较其字典序:

找到最小的满足 ai,paj,pa_{i,p} \neq a_{j, p} 的下标 pp,比较 ai,pa_{i, p}aj,pa_{j, p} 的大小:

  • 如果 ai,p<aj,pa_{i,p} < a_{j, p},则称 aia_i 的字典序比 aja_j 的小。
  • 如果 ai,p>aj,pa_{i,p} > a_{j, p},则称 aia_i 的字典序比 aja_j 的大。

可以证明,在本题的限制下,这样的 pp 一定存在。