AtCoder Grand Contest 002

C - Knot Puzzle


Time limit時間制限 : 2sec / Memory limitメモリ制限 : 256MB

問題文

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

他に例えば、3412 の順に出力しても正解となります。

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.


Submit提出する