Hide

Problem A
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:

$\includegraphics[width=0.5\textwidth ]{pipe_rotation_1.png}$

(A) Nothing
(B) Straight pipe (pipes leaving through two opposite edges)
(C) Elbow-shaped pipe (pipes leaving through two adjacent edges)
(D) Four-way pipe (pipes leaving through all four edges)

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:

$\includegraphics[width=0.28\textwidth ]{pipe_rotation_2}$ Fig 1. Invalid example, two sudden dead-ends.

$\includegraphics[width=0.28\textwidth ]{pipe_rotation_3}$ 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.

Sample Input 1	Sample Output 1
2 2 CC CC	Possible

Sample Input 2	Sample Output 2
2 2 CC CB	Impossible

Sample Input 3	Sample Output 3
3 3 CCC CCC CCC	Impossible

Sample Input 4	Sample Output 4
3 4 CBCA BCDC CCCC	Possible

Sample Input 5	Sample Output 5
5 2 CC CC AA CC CC	Possible

Problem APipe Rotation

Input

Output

Problem A
Pipe Rotation