AT_s8pc_6_e 90-degree Rotations

[problemUrl]: https://atcoder.jp/contests/s8pc-6/tasks/s8pc_6_e $ H\ \times\ W $ のマス目で表されるボードがあります。マス目の $ i\ (1\ \leq\ i\ \leq\ H) $ 行目で $ j\ (1\ \leq\ j\ \leq\ W) $ 列目のマスを $ (i,\ j) $ とします。 いくつかのマスにはコインがあります。$ S_{i,\ j} $ = `o` のとき、マス $ (i,\ j) $ に $ 1 $ つだけコインがあり、`x` のときコインがありません。 ロボットがコインのあるマスから上下左右のいずれかの方向を向いてスタートします。スタート位置と方向は E869120 君が自由に決めることができます。 その後、E869120 君は次の操作を繰り返します。 - その場にあるコインを取った後、$ 90 $ 度左回転または $ 90 $ 度右回転し、向いている方向に $ 1 $ マス以上進んだコインのある位置までジャンプする。 スタートする位置と方向、ジャンプする位置、回転する方向をうまく決めたときに、E869120 君はすべてのコインを回収することができるでしょうか？

入力は以下の形式で標準入力から与えられます。 > $ H $ $ W $ $ S_{1,\ 1}S_{1,\ 2}S_{1,\ 3}...S_{1,\ W} $ $ S_{2,\ 1}S_{2,\ 2}S_{2,\ 3}...S_{2,\ W} $ : : : $ S_{H,\ 1}S_{H,\ 2}S_{H,\ 3}...S_{H,\ W} $

コインをすべて回収する方法があるならば `Possible`、どのような行動を取ってもコインをすべて回収できないならば `Impossible` と出力してください。

### 制約 - $ 2\ \leq\ H\ \leq\ 100 $ - $ 2\ \leq\ W\ \leq\ 100 $ - $ S_{i,\ j} $ は `o` または `x` のいずれか - 最低 $ 1 $ つのコインがボード上にある ### 部分点 この問題はいくつかの小課題に分けられ、その小課題のすべてのテストケースに正解した場合に「この小課題に正解した」とみなされます。 提出したソースコードの得点は、正解した小課題の点数の合計となります。 1. (100 点)：$ N\ \leq\ 8 $ 2. (110 点)：$ N\ \leq\ 16 $ 3. (150 点)：$ H\ =\ 2 $ 4. (440 点)：追加の制約はない。 ただし、ここで $ N $ は「マス目上にあるコインの枚数」とします。 ### Sample Explanation 1 次のような順序でロボットを動かすと、すべてのコインを回収することができます。 !\[ \](https://img.atcoder.jp/s8pc-6/eed0ef22349faee776bece08b515c07f.png) ### Sample Explanation 2 次のような順序でロボットを動かすと、すべてのコインを回収することができます。 !\[ \](https://img.atcoder.jp/s8pc-6/838ec7b3444a622ddc15b1ab87e322d5.png) ### Sample Explanation 3 どのようなロボットの動かし方をしても、すべてのコインを回収することができません。 ### Sample Explanation 4 この場合も、どのようなロボットの動かし方をしても、すべてのコインを回収することができません。