Permutation Shuffle Inversion

Kaikai and Fanfan have n cards (numbered from \(1,2,\dots,n\)) and a shuffling machine. It is given that \(n\) is odd. The shuffling machine operates as follows: 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 passing through the machine, the card at position \(i\) becomes \(k\).

Initially, Kaikai writes down a random permutation \(a_1,a_2,\dots,a_n\) of the numbers \(1,2,\dots,n\). Then he arranges the cards in the following way: for \(1 \le i \le n-1\), the card at position \(a_i\) is \(a_{i+1}\), and the card at position \(a_n\) is \(a_1\). This produces an initial order of cards \(x_1,x_2,\dots,x_n\). After that, he feeds this arrangement into the shuffling machine for \(s\) times to obtain the final order \(p_1,p_2,\dots,p_n\).

Your task is: Given the final order \(p_1,p_2,\dots,p_n\) and the number of shuffles \(s\), recover the initial order \(x_1,x_2,\dots,x_n\>.

The shuffling machine transforms the arrangement by applying the operation \[ f(x)[i]=x[x[i]] \quad (1\le i\le n), \]for an arrangement \(x\). Since the machine is applied \(s\) times, the final order is given by \[ p = f^s(x)=x^{2s}, \]where the exponent denotes permutation composition. Moreover, from the way \(x\) is constructed, it is a cyclic permutation of length \(n\). It is guaranteed that \(\gcd(2s, n)=1\); hence, the equation \[ (x)^{2s}=p \quad \Longrightarrow \quad x=p^r, \]has a unique solution for \(x\), where \(r\) is the multiplicative inverse of \(2s\) modulo \(n\): \[ 2s\cdot r\equiv 1\pmod{n}. \]

To solve the problem, compute \(r\) and then, for each position \(i\), let \(x[i]\) be the result of applying the permutation \(p\) consecutively \(r\) times starting from \(i\). You may find it useful to decompose \(p\) into cycles. For a cycle of length \(L\), if an element appears in position \(j\) in the cycle then its image under \(p^r\) is the element at position \((j+r)\bmod L\) within that cycle.

inputFormat

The first line contains two integers \(n\) and \(s\) (with \(n\) odd and \(\gcd(2s,n)=1\)).

The second line contains \(n\) space-separated integers \(p_1,p_2,\dots,p_n\) representing the final order of the cards.

outputFormat

Output a single line with \(n\) space-separated integers \(x_1,x_2,\dots,x_n\), representing the initial order of the cards.

sample

5 1
3 4 5 1 2

2 3 4 5 1