P1088 [NOIP 2004 Junior] Martians

Humans have finally set foot on Mars and met the mysterious Martians. Humans and Martians cannot understand each other's language, but our scientists invented a way to communicate using numbers. The method is as follows: first, the Martian tells the human scientist a very large number. After deciphering its meaning, the scientist adds a very small number to it and tells the result to the Martian as the human's reply. Martians represent numbers in a very simple way—by bending their fingers. A Martian has only one hand, but this hand has thousands upon thousands of fingers arranged in a line, numbered $1,2,3,\cdots$. Any two fingers can be swapped arbitrarily, and this is how they count. A Martian demonstrated finger counting using a human hand. If the five fingers—thumb, index, middle, ring, and little finger—are numbered $1,2,3,4$ and $5$, then when they are in normal order, they form the $5$-digit number $12345$. If you swap the ring and little finger, you get $12354$. If you completely reverse the order of the five fingers, you get $54321$. Among all $120$ possible $5$-digit numbers that can be formed, $12345$ is the smallest and represents $1$; $12354$ is the second smallest and represents $2$; $54321$ is the largest and represents $120$. The table below shows the $6$ possible $3$-digit numbers when there are only $3$ fingers, and the numbers they represent: | Three-digit number | Represented number | |:-:|:-:| | $123$ | $1$ | | $132$ | $2$ | | $213$ | $3$ | | $231$ | $4$ | | $312$ | $5$ | | $321$ | $6$ | Now you have the honor of being the first human to communicate with a Martian. A Martian will show you his fingers, and the scientists will tell you a small number to add. Your task is to add the number represented by the Martian’s fingers to the number given by the scientists, and then rearrange the Martian’s fingers according to the result. The input guarantees that the result will not exceed the range representable by the Martian’s fingers.

There are three lines. The first line contains a positive integer $N$, the number of the Martian’s fingers ($1 \le N \le 10000$). The second line contains a positive integer $M$, the small integer to add ($1 \le M \le 100$). The third line contains a permutation of the $N$ integers from $1$ to $N$, separated by spaces, representing the order of the Martian’s fingers.

Output $N$ integers, the new order of the Martian’s fingers after the change. Separate adjacent numbers with a single space, and do not print extra spaces.

For $30\%$ of the testdata, $N \le 15$. For $60\%$ of the testdata, $N \le 50$. For $100\%$ of the testdata, $N \le 10000$. NOIP 2004 Junior Problem 4. Translated by ChatGPT 5