← 返回题目列表

AtCoder · agc002_c

C. 结拼图

中文机器翻译题面 查看原题

问题陈述

我们有 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.