Problem H
Pipe Rotation

The four ninja turtles: Leonardo, Donatello, Michelangelo, and Raphael are seeking a new home in Manhattan, New York City. The turtles don’t like sudden dead-ends in their home. Fortunately, the government recently installed a new sewage system where pipes can be rotated! The turtles needs your help finding a suitable home, so they’re willing to provide you a grid of the current layout of the sewage system.

The grid consists of $N$ rows and $M$ columns. The cell $G_{i,j}$ will consist of one of four pipes, encoded as a letter between “A" and “D". These pipes can be rotated by any multiple of $90$ degrees:

Determine whether it’s possible to rotate the cells such that the pipes all line up with one another. In particular, for each edge shared by a pair of adjacent cells, there must either be a pipe on both sides of that edge, or on neither side. And for each of the $2 \cdot (N + M)$ outer edges of the grid, there must be no pipe leaving through that edge. Below are examples:

Fig 1. Invalid example, two sudden dead-ends.

Fig 2. Valid example, no sudden dead-ends.

Input

The first line of input consists of two space-separated integers, $N$ and $M$ ($1 \leq N, M \leq 100$).
$N$ lines follow, the $i$th of which consists of $M$ characters $G_{i,1}, G_{i,2}, G_{i,j}, \dots , G_{i,M}$ and $G_{i,j} \in \{ A,B,C,D\} $ (for $i = 1..N$).

Output

Print, on a single line, a single string, either “Possible" if it’s possible to produce a valid configuration of pipes, or “Impossible" otherwise.

2 2
CC
CC

Possible

2 2
CC
CB

Impossible

3 3
CCC
CCC
CCC

Impossible

3 4
CBCA
BCDC
CCCC

Possible

5 2
CC
CC
AA
CC
CC

Possible