题目描述

$N$ 箇所のオアシスが数直線上に並んでおり、左から $i$ 番目のオアシスは座標 $x_i$ にあります。

ラクダはこれらのオアシス全てを訪れたいです。 ラクダははじめ、体積 $V$ のこぶを持っています。こぶの体積を $v$ としたとき、ラクダは水を最大で $v$ 蓄えることができます。ラクダはオアシスにいるときのみ、水を補給することができます。オアシスでは蓄えられるだけ水を補給することができ、同じオアシスで何回でも水を補給することができます。

ラクダは数直線上を歩くか、ジャンプするかのどちらかの方法で移動することができます。

• ラクダが距離 $d$ だけ歩いたとき、蓄えている水を $d$ だけ消費します。ただし、蓄えられた水の量が負になるようには移動できません。
• 蓄えられた水の量を $v$ として $v\ >\ 0$ のとき、ラクダはジャンプをすることで数直線上の任意の地点へと移動することができます。その後、こぶの体積が $v/2$(小数点以下は切り捨て) となり、蓄えられた水の量が $0$ になります。

ラクダが $1,2,3,...,N$ 番目のオアシスから出発したとき、全てのオアシスを訪れることが可能かどうかをそれぞれ判定してください。

输入格式

入力は以下の形式で標準入力から与えられる。

$N$ $V$ $x_1$ $x_2$ $...$ $x_{N}$

输出格式

答えを $N$ 行に出力せよ。$i$ 行目では $i$ 番のオアシスから出発して全てのオアシスを訪れることが可能ならば Possible と、不可能ならば Impossible と出力せよ。

题目大意

给定 $n$ 个绿洲，第 $i$ 个绿洲的坐标为 $x_i$ ，保证 $-10^{9}\le x_1<x_2...<x_n\le 10^9$

现在有一个人在沙漠中进行旅行，他初始的背包的水容积为 $V$ 升，同时他初始拥有 $V$ 升水 ，每次到达一个绿洲时，他拥有的水的量将自动重置为容积上限（可以使用多次）。他现在可以选择两个操作来进行旅行：

$1.$ 走路，行走距离为 $d$ 时，需要消耗 $d$ 升水。清注意，任意时刻你拥有的水的数量不能为负数。

$2.$ 跳跃，令 $v$ 为你当前拥有的水量，若 $v>0$，则你可以跳跃至任意一个绿洲，然后重置容积上界和所拥有的水量为 $v/2$ （向下取整）。

对于每一个 $i$ 满足 $1\le i\le n$ ，你需要求解，当你在第 $i$ 个绿洲作为起点时，你能否依次遍历其他所有绿洲。如果可以，输出 Possible，否则输出 Impossible。

3 2
1 3 6

Possible
Possible
Possible

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

Impossible
Possible
Possible
Possible
Possible
Possible
Impossible

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

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

提示

制約

• $2\ ≦\ N,V\ ≦\ 2\ ×\ 10^5$
• $-10^9≦\ x_1\ <\ x_2\ <\ ...\ <\ x_N\ ≦10^9$
• $V,\ x_i$ はいずれも整数

Sample Explanation 1

以下のように移動することで、$1$ 番のオアシスから出発して全てのオアシスを訪れることが可能です。 - $1$ 番のオアシスから $2$ 番のオアシスへと歩いて移動する。蓄えられた水の量は $0$ となる。 - $2$ 番のオアシスで水を補給する。蓄えられた水の量は $2$ となる。 - $2$ 番のオアシスから $3$ 番のオアシスへとジャンプして移動する。蓄えられた水の量は $0$ となり、こぶの体積は $1$ となる。

Sample Explanation 2

オアシスは何度訪れても構いません。