P5794 [THUSC 2015] Decryption Operation

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: ```plain 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: ```plain .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.

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 a single line containing $N$ integers separated by spaces, representing the number of each character in the original string before encryption in order.

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