P2227 [HNOI2001] Shuffling Machine

Kaikai and Fanfan have $n$ cards (numbered $1,2,\ldots,n$ in order) and a shuffling machine. Assume $n$ is odd. The shuffling machine performs the following operation: for every position $i$ ($1\le i\le n$), if the card at position $i$ is $j$, and the card at position $j$ is $k$, then after running the machine, the card at position $i$ will be $k$. Kaikai first writes down a random permutation of $1,2,\ldots,n$: $a_1,a_2,\ldots,a_n$. He then arranges the deck as follows: put card $a_{i+1}$ at position $a_i$ (for $1\le i\le n-1$), and put card $a_1$ at position $a_n$. After this arrangement, the deck order is $x_1,x_2,\ldots,x_n$. Then he runs the shuffling machine $s$ times to obtain the order $p_1,p_2,\ldots,p_n$. Now Kaikai tells Fanfan the final order and the number of shuffles, and asks Fanfan to determine the initial order $x_1,x_2,\ldots,x_n$.

The first line contains integers $n$ and $s$. The second line contains the final order of the cards $p_1,p_2,\ldots,p_n$.

Output one line: the initial order $x_1,x_2,\ldots,x_n$.

#### Constraints For $100\%$ of the testdata, it is guaranteed that $1\le n,s\le 10^3$. The testdata guarantees that, starting from $i=1$, let the number on the $i$-th card be $j$, then assign $i=j$ and continue this process; eventually, all cards will be visited. Translated by ChatGPT 5