Time Limit: 2.5 sec / Memory Limit: 256 MB
問題文
joisinoお姉ちゃんの次の仕事は、ゲームのテストプレイである。
このゲームでは、主人公は情報を得るために、様々な村を訪れる。
村人から情報を得るには、適切に貢ぎ物をいくつか選び、村に捧げなくてはならない(ここで、個の貢物を捧げても、すなわち何も捧げなくてもよい)。
貢ぎ物の種類は種類あり、の番号がつけられている。
また、村は個あり、の番号がつけられている。
そして、それぞれの村には、貢ぎ物に関する掟がある。
二つ以上の村が、同じ掟を持つことはない。
この掟は、ある二つの「条件」を同時に満たしてはならないと言うものである。
「条件」とは、「ある貢ぎ物を捧げる」、もしくは、「ある貢ぎ物を捧げない」、というものである。
さらに、ストーリーが進行するに連れ、村の合併が行われる。
回目の合併では、村と村が合併し、村になる。
合併の際には必ず、村と村が存在することが保証され、また合併のあとは、村と村は消滅する。
この時、新しくできた村には、合併元の村の掟がすべて残る。
村の合併は、存在する村が村の一つになるまで行われる。
村〜村には、掟をすべて守る貢物の組み合わせが存在するが、村〜村では、掟が互いに矛盾し、掟をすべて守るような貢物の組み合わせが存在しないかもしれない。
joisinoお姉ちゃんの仕事は、村〜村について、掟をすべて守るような貢物の組み合わせがあるかどうかを判定するプログラムを作ることである。
入力
入力は以下の形式で標準入力から与えられる。
: :
- 行目には、貢物の種類の数を表す整数と、村の数を表す整数が与えられる。
- 続く行のうち行目には、番目の村の掟を表す整数。が与えられる。
- ここで、はそれぞれ、「条件」を表しており、2つの条件を同時に満たしてはならないというのが、村の掟である。
- が正のときは、貢物を捧げるという条件を表しており、が負のときは、貢物を捧げないという条件を表している。についても同様である。
- 続く行のうち行目には、合併する村を示す整数が与えられる。
配点
この問題には部分点が設定されている。
出力
出力は行からなる。
行目には、村について、掟をすべて守るような貢物の組み合わせがある場合は、ない場合はと出力せよ。
入力例1Copy
3 4 1 2 -2 -3 -1 3 1 -2 1 3 2 5 6 4
出力例1Copy
Possible Possible Possible
例えば、村には何も捧げないことができ、村には{貢物と貢物}を捧げることができ、村には{貢物}を捧げることができる。
入力例2Copy
3 4 -1 -2 2 3 1 -2 2 -3 1 4 2 5 6 3
出力例2Copy
Possible Possible Impossible
入力例3Copy
4 20 3 -2 4 -3 3 -1 -2 -3 -1 2 2 -4 2 -3 4 -1 1 4 -1 -3 4 2 1 -3 -2 -1 2 3 3 -4 -4 -2 -4 1 -1 -4 2 1 -4 -3 1 11 16 2 6 20 8 12 22 15 18 5 23 7 9 10 13 26 19 21 4 3 28 31 14 24 27 30 29 25 17 34 36 32 35 33 37 38
出力例3Copy
Possible Possible Possible Possible Possible Possible Possible Possible Possible Possible Possible Possible Possible Possible Possible Possible Impossible Possible Impossible