Time Limit: 2 sec / Memory Limit: 256 MB
問題文
N 本のロープがあります。 ロープは 1 から N まで番号が振られています。 ロープ i の長さは a_i です。
最初、1≤i≤N-1 について、ロープ i の右端とロープ i+1 の左端が結ばれています。 高橋君は次の操作を N-1 回行い、すべての結び目をほどこうとしています。
- ひと繋がりのロープのうち、長さの総和が L 以上のものをひとつ選ぶ。 選んだひと繋がりのロープに結び目があれば、結び目のうちどれかひとつをほどく。
高橋君は結び目をほどく順番を工夫し、すべての結び目をほどくことができるでしょうか? 可能か判定し、可能ならば結び目をほどく順番をひとつ求めてください。
制約
- 2≤N≤10^5
- 1≤a_i≤10^9
- 1≤L≤10^9
- 入力はすべて整数である。
入力
入力は以下の形式で標準入力から与えられる。
N L a_1 a_2 ... a_N
出力
すべての結び目をほどくことができないならば、Impossible
を出力せよ。
すべての結び目をほどくことができるならば、Possible
を出力した後、N-1 行出力せよ。 このうち j 行目には、j 回目の操作でほどく結び目の番号を出力せよ。 ただし、ロープ i の右端とロープ i+1 の左端を結ぶものを結び目 i とする。
入力例1
3 50 30 20 10
出力例1
Possible 2 1
先に結び目 1 をほどくと、結び目 2 をほどけなくなってしまいます。
入力例2
2 21 10 10
出力例2
Impossible
入力例3
5 50 10 20 30 40 50
出力例3
Possible 1 2 3 4
他に例えば、3,4,1,2 の順に出力しても正解となります。
Problem Statement
We have N pieces of ropes, numbered 1 through N. The length of piece i is a_i.
At first, for each i (1≤i≤N-1), piece i and piece i+1 are tied at the ends, forming one long rope with N-1 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 L, then untie one of its knots.
Is it possible to untie all of the N-1 knots by properly applying this operation? If the answer is positive, find one possible order to untie the knots.
Constraints
- 2≤N≤10^5
- 1≤L≤10^9
- 1≤a_i≤10^9
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N L a_1 a_2 ... a_n
Output
If it is not possible to untie all of the N-1 knots, print Impossible
.
If it is possible to untie all of the knots, print Possible
, then print another N-1 lines that describe a possible order to untie the knots. The j-th of those N-1 lines should contain the index of the knot that is untied in the j-th operation. Here, the index of the knot connecting piece i and piece i+1 is i.
If there is more than one solution, output any.
Sample Input 1
3 50 30 20 10
Sample Output 1
Possible 2 1
If the knot 1 is untied first, the knot 2 will become impossible to untie.
Sample Input 2
2 21 10 10
Sample Output 2
Impossible
Sample Input 3
5 50 10 20 30 40 50
Sample Output 3
Possible 1 2 3 4
Another example of a possible solution is 3, 4, 1, 2.