Description

For a string of length $N$, we append a special character . to the end of the string. Then we treat the string as a cycle. Starting from positions $1,2,3,\ldots,N+1$, read $N+1$ characters each time, and we can obtain $N+1$ strings.

For example, for the string ABCAAA, we can get these $N+1$ strings:

ABCAAA.
BCAAA.A
CAAA.AB
AAA.ABC
AA.ABCA
A.ABCAA
.ABCAAA

Next, we sort these $N+1$ strings in lexicographical order from small to large (note that the special character . is lexicographically smaller than any other character). The result is:

.ABCAAA
A.ABCAA
AA.ABCA
AAA.ABC
ABCAAA.
BCAAA.A
CAAA.AB

Finally, take the last character of each of the sorted $N+1$ strings, and concatenate them in order into a new string. That is, the last column of the table above, which is the encrypted ciphertext AAAC.AB.

Please recover the string before encryption from the encrypted ciphertext.

Input Format

The first line contains two integers $N,M$, representing the length of the string before encryption and the size of the character set. The characters are numbered by integers $1,2,3,\ldots,M$, and the appended special character . is numbered by $0$.

The second line contains $N+1$ integers, representing the encrypted string.

Output Format

Output a single line containing $N$ integers separated by spaces, representing the number of each character in the original string before encryption in order.

6 3
1 1 1 3 0 1 2

1 2 3 1 1 1

Hint

For the $i$-th test point ($i=1 \sim 4$), $N=5\times (i+1),M\leq 3$.

For test points $5\sim 6$, $N,M\leq 50$, and all characters in the string are distinct.

For test points $7\sim 8$, $N,M\leq 1000$, and all characters in the string are distinct.

For test points $9\sim 12$, $N,M\leq 1000$.

For test points $13\sim 20$, $N,M\leq 200000$.

Translated by ChatGPT 5