# Dance Reconstruction (Hard)

*Note that this is a harder version of problem dance. The
change to the previous version is marked in bold.*

Marek loves dancing and he has danced a lot in the last couple of years. He has actually danced so much that he became too good in all of the traditional dances like swing, salsa, ballroom and hip-hop and now all partners he dances with can not keep up with him. Therefore he started to invent his own dances and even tries to convince other people to dance these new dances with him.

Marek got really excited when he heard about the coming
wedding of his best friend Miroslav. For a whole month he
worked on a special dance for the wedding. The dance was
performed by $N$ people
and there were $N$ marks
on the floor. There was an arrow from each mark to another mark
and every mark had exactly one incoming arrow. **Marek did not want anyone to stand on one place the whole
time, so no arrow pointed from a mark back to the same
mark.**

At the wedding, every person first picked a mark on the floor and no 2 persons picked the same one. Then Marek played some music and every 10 seconds there was a loud signal when all dancers had to move along the arrow on the floor to another mark. The placement of the marks was such that everybody could follow the arrow to the next mark in 10 seconds without any trouble.

A year has passed since Miroslav’s wedding and another wedding is coming up. Marek would like to do a similar dance at this wedding as well. He lost all the drawings he had, but luckily he found two photos from exactly when the dance started and when it ended. Marek also remembers that the signal was triggered $K$ times during the time the song was played, so people moved $K$ times along the arrows.

Given the two photos, can you help Marek reconstruct the
arrows on the floor **so that each arrow connects
two different marks**? On the two photos it can be seen for
every person to which position he or she moved. Marek therefore
numbered the people in the first photo from $1$ to $N$ and then wrote the number of the
person whose place they took in the second photo.

Marek’s time is running out, so he is interested in any placement of arrows that could produce the two photos.

## Input

The first line of the input contains two integers $N$ and $K$, $2 \le N \le 10\, 000, 1\le K \le 10^9$. The second line of the input contains $N$ space separated integers $a_1, \dots , a_ N$, denoting that dancer number $i$ ended at the place of dancer number $a_ i$. You may assume that $1 \le a_ i \le N$ for all $i$ and every number between $1$ and $N$ inclusive appears exactly once in the sequence.

## Output

If it is impossible to find a placement of arrows such that
the dance performed $K$
times would produce the two photos, print “`Impossible`”. Otherwise print $N$ numbers on a line, the
$i$-th number denoting to
which person the arrow leads from person number $i$. **Note that the
$i$-th number cannot be
$i$, because then the
person would not move the whole time.** If there are more
solutions, you can print any one.

Sample Input 1 | Sample Output 1 |
---|---|

6 2 3 4 5 6 1 2 |
5 6 1 2 3 4 |

Sample Input 2 | Sample Output 2 |
---|---|

4 2 3 4 1 2 |
2 3 4 1 |

Sample Input 3 | Sample Output 3 |
---|---|

3 2 1 2 3 |
Impossible |