P9472 [yLOI2022] Pillow of Ten Thousand Dreams

> In the dim flow of years, stars shift and things change, singing praise of youth. > In the dim crowd, one glance sees through it all; sun and moon vanish without a trace. > In the dim fate between you and me, our hearts understand each other—far more than ten thousand dreams. > Forgetting ourselves in this long-awaited reunion. > In the dim world, clouds and mist surge; shoulders brush and people crowd. > In the dim chorus of all sounds, unwilling to stay silent, grand without end. > In the dim fate between you and me, sitting face to face across the ends of the earth, our “telepathy” (lingxi) stirs. > And we meet in a space and time just within reach. Yin Lin, “Pillow of Ten Thousand Dreams”. # Background

Daybreak came. Fusu could not resist sleepiness and fell asleep early. In a gravity-less dream, Fusu encountered many floating sequences. They all have the same length, and they are all wonderful geometric sequences. By instinct, Fusu wants to sort these sequences in lexicographical order, but in the dream she lost the ability to think. Please help her. More specifically, there are $n$ sequences numbered from $1$ to $n$: $a_1, a_2, \dots a_n$. Each sequence has length $m + 1$. The $i$-th sequence $a_i$ satisfies the recurrence $a_{i,j} = a_{i,j - 1} \times i$, where $1 \leq j \leq m$. Fusu will tell you the first term $a_{i,0}$ of each sequence, and you need to help her sort these sequences in lexicographical order.

The first line contains two integers, in order, $n$ and $m$. The next $n$ lines each contain one integer. The integer on line $i$ is the first term $a_{i,0}$ of sequence $a_i$.

Output one line with $n$ integers. The $i$-th integer is the **index** of the sequence that is the $i$-th smallest in lexicographical order.

### Explanation for Sample 1 There are two sequences, each of length $2 + 1 = 3$. For the first sequence $a_1$: - Its first term is $a_{1,0} = 1$. - 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$. So sequence $a_1$ is $1, 1, 1$. For the second sequence $a_2$: - Its first term is $a_{2,0} = 2$. - 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$. So sequence $a_2$ is $2, 4, 8$. By lexicographical comparison, $a_1$ is the smallest sequence. Therefore the output is $1$. ### Explanation for Sample 2 Sequence $a_1$ is $1, 1, 1, 1$, and sequence $a_2$ is $-1, -2, -4, -8$. ### Constraints This problem has $10$ test points. The information for each test point is shown in the table below:  Special constraint A: it is guaranteed that all $a_{i,0}$ are equal. Special constraint B: it is guaranteed that all $a_{i,0}$ are pairwise distinct. For all test points, 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$. ### Hint To compare the lexicographical order of two sequences $a_i$ and $a_j$, do the following: Find the **smallest** index $p$ such that $a_{i,p} \neq a_{j,p}$, and compare $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$ must exist. Translated by ChatGPT 5