/ 
Time Limit: 2 sec / Memory Limit: 256 MB
配点 : 1000 点
問題文
N 箇所のオアシスが数直線上に並んでおり、左から i 番目のオアシスは座標 x_i にあります。
ラクダはこれらのオアシス全てを訪れたいです。 ラクダははじめ、体積 V のこぶを持っています。こぶの体積を v としたとき、ラクダは水を最大で v 蓄えることができます。ラクダはオアシスにいるときのみ、水を補給することができます。オアシスでは蓄えられるだけ水を補給することができ、同じオアシスで何回でも水を補給することができます。
ラクダは数直線上を歩くか、ジャンプするかのどちらかの方法で移動することができます。
- ラクダが距離 d だけ歩いたとき、蓄えている水を d だけ消費します。ただし、蓄えられた水の量が負になるようには移動できません。
- 蓄えられた水の量を v として v>0 のとき、ラクダはジャンプをすることで数直線上の任意の地点へと移動することができます。その後、こぶの体積が v/2(小数点以下は切り捨て) となり、蓄えられた水の量が 0 になります。
ラクダが 1,2,3,...,N 番目のオアシスから出発したとき、全てのオアシスを訪れることが可能かどうかをそれぞれ判定してください。
制約
- 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 行目では i 番のオアシスから出発して全てのオアシスを訪れることが可能ならば Possible と、不可能ならば Impossible と出力せよ。
入力例 1
3 2 1 3 6
出力例 1
Possible Possible Possible
以下のように移動することで、1 番のオアシスから出発して全てのオアシスを訪れることが可能です。
- 1 番のオアシスから 2 番のオアシスへと歩いて移動する。蓄えられた水の量は 0 となる。
- 2 番のオアシスで水を補給する。蓄えられた水の量は 2 となる。
- 2 番のオアシスから 3 番のオアシスへとジャンプして移動する。蓄えられた水の量は 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
Score : 1000 points
Problem Statement
There are N oases on a number line. The coordinate of the i-th oases from the left is x_i.
Camel hopes to visit all these oases. Initially, the volume of the hump on his back is V. When the volume of the hump is v, water of volume at most v can be stored. Water is only supplied at oases. He can get as much water as he can store at a oasis, and the same oasis can be used any number of times.
Camel can travel on the line by either walking or jumping:
- Walking over a distance of d costs water of volume d from the hump. A walk that leads to a negative amount of stored water cannot be done.
- Let v be the amount of water stored at the moment. When v>0, Camel can jump to any point on the line of his choice. After this move, the volume of the hump becomes v/2 (rounded down to the nearest integer), and the amount of stored water becomes 0.
For each of the oases, determine whether it is possible to start from that oasis and visit all the oases.
Constraints
- 2 ≤ N,V ≤ 2 × 10^5
- -10^9 ≤ x_1 < x_2 < ... < x_N ≤ 10^9
- V and x_i are all integers.
Input
Input is given from Standard Input in the following format:
N V
x_1 x_2 ... x_{N}
Output
Print N lines. The i-th line should contain Possible if it is possible to start from the i-th oasis and visit all the oases, and Impossible otherwise.
Sample Input 1
3 2 1 3 6
Sample Output 1
Possible Possible Possible
It is possible to start from the first oasis and visit all the oases, as follows:
- Walk from the first oasis to the second oasis. The amount of stored water becomes 0.
- Get water at the second oasis. The amount of stored water becomes 2.
- Jump from the second oasis to the third oasis. The amount of stored water becomes 0, and the volume of the hump becomes 1.
Sample Input 2
7 2 -10 -4 -2 0 2 4 10
Sample Output 2
Impossible Possible Possible Possible Possible Possible Impossible
A oasis may be visited any number of times.
Sample Input 3
16 19 -49 -48 -33 -30 -21 -14 0 15 19 23 44 52 80 81 82 84
Sample Output 3
Possible Possible Possible Possible Possible Possible Possible Possible Possible Possible Possible Possible Impossible Impossible Impossible Impossible