atcoder#AGC002C. [AGC002C] Knot Puzzle
[AGC002C] Knot Puzzle
Problem Statement
We have pieces of ropes, numbered through . The length of piece is .
At first, for each , piece and piece are tied at the ends, forming one long rope with knots. Snuke will try to untie all of the knots by performing the following operation repeatedly:
- Choose a (connected) rope with a total length of at least , then untie one of its knots.
Is it possible to untie all of the knots by properly applying this operation? If the answer is positive, find one possible order to untie the knots.
Constraints
- All input values are integers.
Input
The input is given from Standard Input in the following format:
Output
If it is not possible to untie all of the knots, print Impossible
.
If it is possible to untie all of the knots, print Possible
, then print another lines that describe a possible order to untie the knots. The -th of those lines should contain the index of the knot that is untied in the -th operation. Here, the index of the knot connecting piece and piece is .
If there is more than one solution, output any.
3 50
30 20 10
Possible
2
1
If the knot is untied first, the knot will become impossible to untie.
2 21
10 10
Impossible
5 50
10 20 30 40 50
Possible
1
2
3
4
Another example of a possible solution is , , , .