AtCoder Grand Contest 002
C
Knot Puzzle
AtCoder
⌀ 1570
原题
← BD →
翻译中…

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.

翻译中…

样例

Input #1
3 50
30 20 10
Output #1
Possible
2
1
If the knot $1$ is untied first, the knot $2$ will become impossible to untie.
Input #2
2 21
10 10
Output #2
Impossible
Input #3
5 50
10 20 30 40 50
Output #3
Possible
1
2
3
4
Another example of a possible solution is $3$, $4$, $1$, $2$.
题目信息
题号
agc002_c
时间限制
2 s
内存限制
256 MB

题面与样例版权归 AtCoder 及出题人所有;中文翻译由 AI 生成(CI 管线),如有出入请以原文为准。