1217 - Properly Choosing

時間制限 1 秒 / メモリ制限 64 MB / 得点 10 / Writer ei1903 / x 8 / 統計 /


TLE
1sec
MLE
64MB
得点
10

問題

あなたは N 個の整数を持っている。 i (1 ≤ iN ) 番目の整数は ai である。
Q 回入力される各 xj (1 ≤ jQ) について、 N 個の整数の中から以下の条件をを満たすようにいくつかの整数を選んだ場合、それらの総和を xj にすることができるか判定せよ。

  • 0個以上N個以下の整数を選ぶことができる。
  • 選ぶ整数の値は相異なる。(値の同じものを一度に選んではいけない)
可能なら"Possible"不可能なら"Impossible"と出力せよ。

入力

N Q
a1 a2 ... aN
x1
x2
...
xQ

一行目にあなたが持っている整数の数 N と判定する回数 Qが与えられる。
二行目に あなたが持っている整数 ai N 個入力される。
三行目から Q 行にわたって、判定する整数 xj が与えられる。

出力

Q行にわたって、条件を満たすように N 個の中から整数を選び、その総和を xj にできるなら"Possible"できないなら"Impossible"と出力する。
出力の末尾には改行を入れること。

制約

  • 1 ≤ N ≤ 106
  • 1 ≤ Q ≤ 105
  • -10 ≤ ai ≤ 10
  • -109xj ≤ 109

入出力例

例1

入力

5 3
1 2 3 4 5
10
20
0

出力

Possible
Impossible
Possible

解説

例えば、
1回目 : 1,2,3,4番目の整数を選ぶと総和は10になる。
2回目 : どのように選んでも20にはならない。
3回目 : 1つも選ばなければよい。

例2

入力

10 5
-3 10 9 3 0 7 3 2 -8 -4
30
8
-14
31
-11

出力

Impossible
Possible
Impossible
Possible
Possible