Background

In the mysterious flow of time, stars shift and change, singing praises to youth.
In the crowd, with a glance, the sun and moon vanish without a trace.
Between you and me, in the mysterious, our hearts are in tune, transcending tens of thousands of dreams.
Forgetting emotions in this long-awaited reunion.
In the vastness of heaven and earth, clouds surge, jostling and pressing close.
In the silence of all things, they refuse to be silent, grand and infinite.
Between you and me, sitting across天涯, the moment our hearts move,
We meet in the space just inches apart.

By Yin Lin, "Pillow of Ten Thousand Dreams"

Problem Description

As dawn breaks, Fusu succumbs to drowsiness and drifts into sleep. In a dream where gravity is lost, Fusu encounters many floating sequences, all of equal length and all beautiful geometric progressions! Driven by instinct, Fusu wants to sort these sequences lexicographically, but in the dream, she loses her ability to think. Please help her!

Specifically, there are $n$ sequences numbered from $1$ to $n$, denoted as $a_1, a_2, \dots, a_n$, each with a length of $m + 1$. The $i$-th sequence $a_i$ satisfies the recurrence relation $a_{i,j} = a_{i,j - 1} \times i$, where $1 \leq j \leq m$. Fusu will tell you the initial term $a_{i,0}$ of each sequence, and you need to help her sort these sequences lexicographically.

Input Format

The first line of input contains two integers, $n$ and $m$, representing the number of sequences and the length of each sequence minus one, respectively.
The following $n$ lines each contain an integer, where the $i$-th line represents the initial term $a_{i,0}$ of the sequence $a_i$.

Output Format

Output a single line containing $n$ integers, where the $i$-th integer represents the index of the sequence that is the $i$-th smallest in lexicographical order.

Sample Input and Output

Sample Input #1

2 2
1
2

Sample Output #1

1 2

Sample Input #2

2 3
1
-1

Sample Output #2

2 1

Sample Input #3

2 2
1
1

Sample Output #3

1 2

Sample Input #4

See the attached file B4.in

Sample Output #4

See the attached file B4.ans

Notes

Sample 1 Explanation

There are two sequences, each with a length of $2+1=3$.

For the first sequence $a_1$:
- The initial term $a_{1,0} = 1$ is known.
- Using $a_{i,j} = a_{i,j - 1} \times i$, with $i=1, j=1$, we get $a_{1,1} = a_{1,0} \times 1 = 1$.
- Using $a_{i,j} = a_{i,j - 1} \times i$, with $i=1, j=2$, we get $a_{1,2} = a_{1,1} \times 1 = 1$.

Thus, sequence $a_1$ is $1,1,1$.

For the second sequence $a_2$:
- The initial term $a_{2,0} = 2$ is known.
- Using $a_{i,j} = a_{i,j - 1} \times i$, with $i=2, j=1$, we get $a_{2,1} = a_{2,0} \times 2 = 2 \times 2 = 4$.
- Using $a_{i,j} = a_{i,j - 1} \times i$, with $i=2, j=2$, we get $a_{2,2} = a_{2,1} \times 2 = 4 \times 2 = 8$.

Thus, sequence $a_2$ is $2,4,8$.

Comparing lexicographically, sequence $a_1$ is the smallest. Therefore, output $1$.

Sample 2 Explanation

Sequence $a_1$ is $1,1,1,1$, and sequence $a_2$ is $-1, -2, -4, -8$.

Data Constraints

This problem consists of $10$ test cases, with the details of each test case as shown in the table below:

Special Condition A: All $a_{i,0}$ are guaranteed to be equal.
Special Condition B: All $a_{i,0}$ are guaranteed to be distinct.

For all test cases, it is guaranteed that $1 \leq n \leq 10^5$, $1 \leq m \leq 10^9$, and $1 \leq |a_{i,0}| \leq 10^9$.

Hints

To compare two sequences $a_i$ and $a_j$ lexicographically:

Find the smallest index $p$ where $a_{i,p} \neq a_{j,p}$, and compare the values of $a_{i,p}$ and $a_{j,p}$:

• If $a_{i,p} < a_{j,p}$, then $a_i$ is lexicographically smaller than $a_j$.
• If $a_{i,p} > a_{j,p}$, then $a_i$ is lexicographically larger than $a_j$.

It can be proven that under the constraints of this problem, such a $p$ always exists.

见题面 Input 部分

见题面 Output 部分