atcoder#AGC002C. [AGC002C] Knot Puzzle

[AGC002C] Knot Puzzle

問題文

NN 本のロープがあります。 ロープは 11 から NN まで番号が振られています。 ロープ ii の長さは aia_i です。

最初、1iN11 \leq i \leq N-1 について、ロープ ii の右端とロープ i+1i+1 の左端が結ばれています。 高橋君は次の操作を N1N-1 回行い、すべての結び目をほどこうとしています。

  • ひと繋がりのロープのうち、長さの総和が LL 以上のものをひとつ選ぶ。 選んだひと繋がりのロープに結び目があれば、結び目のうちどれかひとつをほどく。

高橋君は結び目をほどく順番を工夫し、すべての結び目をほどくことができるでしょうか? 可能か判定し、可能ならば結び目をほどく順番をひとつ求めてください。

制約

  • 2N1052 \leq N \leq 10^5
  • 1ai1091 \leq a_i \leq 10^9
  • 1L1091 \leq L \leq 10^9
  • 入力はすべて整数である。

入力

入力は以下の形式で標準入力から与えられる。

NN LL

a1a_1 a2a_2 ...... aNa_N

出力

すべての結び目をほどくことができないならば、Impossible を出力せよ。

すべての結び目をほどくことができるならば、Possible を出力した後、N1N-1 行出力せよ。 このうち jj 行目には、jj 回目の操作でほどく結び目の番号を出力せよ。 ただし、ロープ ii の右端とロープ i+1i+1 の左端を結ぶものを結び目 ii とする。

入力例1

3 50
30 20 10

出力例1

Possible
2
1

先に結び目 11 をほどくと、結び目 22 をほどけなくなってしまいます。

入力例2

2 21
10 10

出力例2

Impossible

入力例3

5 50
10 20 30 40 50

出力例3

Possible
1
2
3
4

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