问题陈述
我们有 N 绳索,已编号 1 通过 N。片长 i is a_i.
首先,对于每个 i (1≤i≤N-1),一块 i 和一块 i+1 两端系在一起,形成一根长绳 N-1 节。 Snuke 将尝试通过重复执行以下操作来解开所有的结:
- 选择一条(连接的)绳子,总长度至少为 L,然后解开其中一个结。
是否可以全部解开 N-1 通过正确应用此操作来结吗?如果答案是肯定的,请找出一种可能的顺序来解开这个结。
约束
- 2≤N≤10^5
- 1≤L≤10^9
- 1≤a_i≤10^9
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N L a_1 a_2 ... a_n
输出
如果无法解开所有 N-1 结,打印 Impossible.
如果可以解开所有的结,则打印 Possible,然后打印另一个 N-1 行描述了解开结的可能顺序。的 j- 第一个 N-1 行应包含在中解开的结的索引 j-第次操作。这里,结连接件的索引 i 和一块 i+1 is 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.