← 返回题目列表

AtCoder · agc012_e

E. 骆驼和绿洲

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

分数: 1000 点

问题陈述

有 N 数轴上的绿洲。的坐标 i左边起第 绿洲 是 x_i.

骆驼希望参观所有这些绿洲。 最初,他背上驼峰的体积是 V。当驼峰的体积为 v,最多体积水 可以存储 v 。仅在绿洲供应水。他可以在绿洲中获取尽可能多的水,并且同一个绿洲可以多次使用。

骆驼可以通过步行或跳跃在线路上移动:

  • 步行的距离 d 消耗水量 d 来自驼峰。导致储存水量为负值的步行是不可能进行的。
  • 让 v 是当前储存的水量。当 v>0,骆驼可以跳到他选择的线上的任何点。在此移动之后,驼峰的体积变为 v/2 (向下舍入到最接近的整数),储存的水量变为 0.

对于每个绿洲,确定是否可以从该绿洲出发并访问所有绿洲。

约束

  • 2 ≤ N,V ≤ 2 × 10^5
  • -10^9 ≤ x_1 < x_2 < ... < x_N ≤ 10^9
  • V 和 x_i 均为整数。

输入

输入由标准输入按以下格式给出:

N V
x_1 x_2 ... x_{N}

输出

打印 N 行。的 i- 第行应包含 Possible 如果可以从 i- 第一个绿洲并访问所有绿洲,并且 Impossible 否则。


示例输入 1

3 2
1 3 6

示例输出 1

Possible
Possible
Possible

可以从第一个绿洲开始,访问所有绿洲,如下:

  • 从第一个绿洲步行到第二个绿洲。储存的水量变为 0.
  • 在第二个绿洲取水。储存的水量变为 2.
  • 从第二个绿洲跳到第三个绿洲。储存的水量变为 0,驼峰的体积变为 1.

示例输入 2

7 2
-10 -4 -2 0 2 4 10

示例输出 2

Impossible
Possible
Possible
Possible
Possible
Possible
Impossible

绿洲可以被访问任意多次。


示例输入 3

16 19
-49 -48 -33 -30 -21 -14 0 15 19 23 44 52 80 81 82 84

示例输出 3

Possible
Possible
Possible
Possible
Possible
Possible
Possible
Possible
Possible
Possible
Possible
Possible
Impossible
Impossible
Impossible
Impossible