分数: 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