Description

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

具体地，有 $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 Format

输入的第一行是两个整数，依次表示 $n$ 和 $m$。
接下来 $n$ 行，每行一个整数，第 $i$ 行的整数表示数列 $a_i$ 的首项 $a_{i,0}$。

Output Format

输出一行 $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

Hint

样例 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$ 一定存在。