问题描述

nck { 宽度: 30px; 高度: 自动; }

我们有一个 $H$ 行 $W$ 列的网格。初始时，石头位于左上角的单元格。Shik试图将石头移动到右下角的单元格。在每一步中，他可以将石头向左、上、右或下移动一个单元格（如果存在此类单元格）。石头可能多次访问一个单元格（包括右下角和左上角的单元格）。

给定一个字符矩阵 $a_{ij}$（$1 \leq i \leq H$，$1 \leq j \leq W$）。在Shik完成所有移动操作之后，$a_{ij}$ 的值为 #，表示石头在移动过程中曾经位于第 $i$ 行第 $j$ 列的单元格上；否则，$a_{ij}$ 的值为 .。请确定是否可能使Shik在所有步骤中仅使用向右和向下的移动。

约束条件

• $2 \leq H, W \leq 8$
• $a_{i,j}$ 可以是 # 或者 .。
• 存在一个有效的移动序列，使得 Shik 可以生成地图 $a$。

输入

输入数据从标准输入读取，格式如下：

$H$ $W$ $a_{11}a_{12}...a_{1W}$ $:$ $a_{H1}a_{H2}...a_{HW}$

输出

如果可能使 Shik 仅使用向右和向下的移动，输出 Possible。否则，输出 Impossible。

样例输入 1

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

样例输出 1

Possible

矩阵可以由一个 $7$ 步的移动序列生成：向右、向下、向右、向下、向右、向下、向右。

样例输入 2

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

样例输出 2

Impossible

样例输入 3

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

样例输出 3

Impossible