Problem C
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 |
