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 deadends 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:


(A) Nothing

(B) Straight pipe (pipes
leaving through two opposite edges)

(C) Elbowshaped pipe
(pipes leaving through two adjacent edges)

(D) Fourway 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 each of the $2 \cdot (N
+ M)$ outer edges of the grid, there must be no pipe
leaving through that edge. Below are examples:
Input
The first line of input consists of two spaceseparated
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
