[yLOI2022] 枕万梦

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