题目描述

有 $N$ 个绿洲沿数轴排列，第 $i$ 个绿洲在坐标 $x_i$ 处。

骆驼想要访问所有这些绿洲。初始时骆驼有体积为 $V$ 的驼峰。将当前驼峰的体积记为 $v$，骆驼最多可储存 $v$ 单位的水。骆驼只能在绿洲补充水。每次在绿洲补水可以将水加满至当前最大容量，每个绿洲可以无数次补水。

骆驼有两种移动方式：步行或跳跃。

• 步行时，骆驼若走 $d$ 距离，则消耗 $d$ 单位水。水量不能为负。
• 只要当前水量 $v>0$，骆驼可以通过跳跃移动到数轴上任何一点。跳跃后，驼峰体积变为 $\left\lfloor v/2 \right\rfloor$（向下取整），水量归零。

请你判断，对每一个 $i=1,2,\dots,N$，如果从第 $i$ 个绿洲出发，是否可以访问所有绿洲。对于每个出发点，输出Possible（可以）或Impossible（不可以）。

输入格式

输入为：

$N\ V\ x_1\ x_2\ \ldots\ x_N$

输出格式

输出 $N$ 行，第 $i$ 行为从第 $i$ 个绿洲出发能否访问所有绿洲。 能则输出 Possible，否则输出 Impossible。

输入输出样例 #1

输入 #1

3 2
1 3 6

输出 #1

Possible
Possible
Possible

输入输出样例 #2

输入 #2

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

输出 #2

Impossible
Possible
Possible
Possible
Possible
Possible
Impossible

输入输出样例 #3

输入 #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

说明/提示

限制

• $2\le N, V\le 2\times 10^5$
• $-10^9\le x_1 < x_2 <\ldots < x_N\le 10^9$
• $V$、$x_i$ 均为整数

样例说明1

如样例1所示，可以如下移动：

• 从第 1 个绿洲步行到第 2 个绿洲，水用完。
• 在第 2 个绿洲补满水（容量 $2$）。
• 从第 2 个绿洲跳跃到第 3 个绿洲，水清零，驼峰体积变为 $1$。

样例说明2

同一个绿洲可以反复到达。

由 ChatGPT 5 翻译