Lexicographical Order of Geometric Sequences

Fusu encountered n geometric sequences in her dream. The i-th sequence, denoted as \(a_i\), has a length of \(m+1\) and is defined by the recurrence relation:

\(a_{i,0} = \text{given},\quad a_{i,j} = a_{i, j-1} \times i \quad (1 \le j \le m)\)

That is, the sequence is:

\(\big[a_{i,0},\; a_{i,0}\times i,\; a_{i,0}\times i^2,\; \dots,\; a_{i,0}\times i^m\big]\).

Your task is to sort these sequences in lexicographical order. In lexicographical order, two sequences \(a = [a_0,a_1,\dots,a_m]\) and \(b = [b_0,b_1,\dots,b_m]\) are compared by finding the smallest index \(k\) (where \(0 \le k \le m\)) such that \(a_k \neq b_k\); the sequence with the smaller \(a_k\) comes first.

If all corresponding terms are equal, the sequences are considered equal. It is guaranteed that the \(i\)-th sequence corresponds to the multiplier i (with indexing starting at 1) and its first term \(a_{i,0}\) is provided. Note that if two sequences have the same initial term, then comparing the second term (which is \(a_{i,0} \times i\)) will determine their order.

Output the indices of the sequences in ascending lexicographical order, separated by a space.

inputFormat

The input consists of two lines:

• The first line contains two integers \(n\) and \(m\) (where \(1 \le n, m \le 10^5\)), representing the number of sequences and the parameter such that each sequence has \(m+1\) terms.
• The second line contains \(n\) integers: \(a_{1,0}, a_{2,0}, \dots, a_{n,0}\), the first term of each sequence.

All numbers are guaranteed to be positive.

outputFormat

Output a single line with \(n\) integers separated by spaces, representing the indices (from 1 to \(n\)) of the sequences sorted in lexicographical order.

sample

2 2
5 1

2 1