AT_agc007_a [AGC007A] Shik and Stone

有一个被划分为纵向 $H$ 行、横向 $W$ 列的棋盘。最初，棋子被放在左上角的格子里。Shikku 将这个棋子每次移动一格，可以向上、下、左、右移动，将其移动到右下角的格子。在这个过程中，棋子可能经过同一个格子多次（包括左上角和右下角的格子）。 给定由字符 $a_{ij}$ 组成的棋盘（$1 \leq i \leq H$，$1 \leq j \leq W$）。当 $a_{ij}$ 为 `#` 时，表示棋子在移动过程中至少经过了第 $i$ 行第 $j$ 列的格子一次（左上角和右下角的格子一定会经过）。当 $a_{ij}$ 为 `.` 时，表示棋子在移动过程中从未经过第 $i$ 行第 $j$ 列的格子。请判断，是否存在一种移动方式，使得棋子在移动过程中始终只向右或向下移动，并且经过的格子与给定的信息一致。

输入以如下格式从标准输入读入。 > $H$ $W$ > $A_{11}A_{12}\ldots A_{1W}$ > $A_{21}A_{22}\ldots A_{2W}$ > $\vdots$ > $A_{H1}A_{H2}\ldots A_{HW}$

如果存在一种移动方式，使得棋子在移动过程中始终只向右或向下移动，并且经过的格子与给定的信息一致，则输出 `Possible`，否则输出 `Impossible`。

## 限制条件 - $2 \leq H, W \leq 8$ - $a_{i,j}$ 只可能为 `#` 或 `.`。 - 保证存在与题目描述及 $a$ 中给出的信息一致的棋子的移动方式。 ## 样例解释 1 如果棋子依次向右、下、右、下、右、下、右移动，则经过的格子与给定的信息一致。 由 ChatGPT 4.1 翻译