H - Shuffling Machine
Editorial
/
KM bought a new card shuffling machine.
According to his hypothesis, everytime you setup N cards and push the switch, it shuffles the cards in a totally same way. More precisely, there exists a sequence of integers a_1, a_2, ..., a_N such that
He wanted to know this sequence, so he setup N cards in the ascending order: 1, 2, ..., N. However, he accidentally pushed the switch K times, and the resulting order of the cards was b_1, b_2, ..., b_N.
But KM says that you can guess a_1, a_2, ..., a_N from b_1, b_2, ..., b_N. Can you do that?
The first line of the input file contains the integers N (1 \leq N \leq 10^5) and K (1 \leq K \leq 10^{18}), separated by a space.
The second line of the input file contains N different integers which denotes b_1, b_2, ..., b_N (1 \leq b_i \leq N) in this order, separated by a space.
If KM's hypothesis seems to be wrong, just print
Time Limit: 1.5 sec / Memory Limit: 93 MB
Description
According to his hypothesis, everytime you setup N cards and push the switch, it shuffles the cards in a totally same way. More precisely, there exists a sequence of integers a_1, a_2, ..., a_N such that
- the 1st card in the resulting order is always the a_1-th card in the initial order,
- the 2nd card in the resulting order is always the a_2-th card in the initial order,
- ..., and so on.
He wanted to know this sequence, so he setup N cards in the ascending order: 1, 2, ..., N. However, he accidentally pushed the switch K times, and the resulting order of the cards was b_1, b_2, ..., b_N.
But KM says that you can guess a_1, a_2, ..., a_N from b_1, b_2, ..., b_N. Can you do that?
Input
The second line of the input file contains N different integers which denotes b_1, b_2, ..., b_N (1 \leq b_i \leq N) in this order, separated by a space.
Output
Impossible
. If there are several possibilities, print Ambiguous
. Otherwise, print N integers which denotes a_1, a_2, ..., a_N in this order, separated by a space.
Sample Input
3 2 3 1 2
Sample Output
2 3 1
Sample Input
3 2 1 3 2
Sample Output
Impossible
Sample Input
4 2 2 1 4 3
Sample Output
Ambiguous