题目描述

有一个被划分为纵向 $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。

样例 1

输入

4 5
##...
.##..
..##.
...##

输出

Possible

样例 2

输入

5 3
###
..#
###
#..
###

输出

Impossible

样例 3

输入

4 5
##...
.###.
.###.
...##

输出

Impossible

说明/提示

限制条件

• $2 \leq H, W \leq 8$
• $a_{i,j}$ 只可能为 # 或 .。
• 保证存在与题目描述及 $a$ 中给出的信息一致的棋子的移动方式。

样例解释 1

如果棋子依次向右、下、右、下、右、下、右移动，则经过的格子与给定的信息一致。

由 ChatGPT 4.1 翻译