Permutation Transformation via Cyclic Adjacent Swaps

You are given a permutation a of length \(n\) containing the integers \(1,2,\dots,n\) exactly once. Also, you are given an integer \(m\) representing the number of operations. In the \(i\)th operation, you swap the two numbers that are the \(\bigl((i-1)\bmod (n-1)+1\bigr)\)th largest and \(\bigl((i-1)\bmod (n-1)+2\bigr)\)th largest in a.

Note that the k-th largest number refers to the number with the \(k\)th highest value. In other words, the largest number is \(n\), the second largest is \(n-1\), and so on. Thus, the operations are performed on fixed pairs:

• Operation 1 swaps \(n\) and \(n-1\).
• Operation 2 swaps \(n-1\) and \(n-2\).
• \(\vdots\)
• Operation \(n-1\) swaps \(2\) and \(1\).

After \(n-1\) operations a complete cycle is done which effectively rotates the positions of the numbers (when tracked by their positions in the original permutation). Formally, if we denote by \(P\) an array of length \(n\) where \(P[1] = pos(n)\), \(P[2] = pos(n-1)\), \(\dots\), \(P[n] = pos(1)\) (with \(pos(x)\) being the index of \(x\) in the permutation), then every full cycle of \(n-1\) operations rotates \(P\) to the left by one position. The remaining \(r = m \bmod (n-1)\) operations then sequentially swap the first \(r\) adjacent pairs in \(P\).

Finally, the final permutation is obtained by placing each number \(n-i+1\) (which originally occupied the \(i\)th position in the descending sorted order) into the updated position \(P[i]\) for \(1 \le i \le n\>.

Your task is to compute and output the final permutation of \(a\) after \(m\) operations.

inputFormat

The first line contains two integers \(n\) and \(m\) (where \(2 \le n \le 10^5\) and \(0 \le m \le 10^9\)).

The second line contains \(n\) integers \(a_1, a_2, \dots, a_n\) representing a permutation of \(1,2,\dots,n\).

outputFormat

Output the final permutation after performing \(m\) operations. Print \(n\) integers in one line separated by spaces.

sample

3 3
2 3 1

2 1 3