Problem Description

There is a board represented by a grid of size $H \times W$. The cell in the $ i $ -th row and $ j $ -th column is denoted as $ (i, j) $.

Some cells contain coins. When $ S_{i, j} $ = o, there is exactly one coin in cell $ (i, j) $, and when $ S_{i, j} $ = x, there is no coin.

A robot starts at a cell with a coin, facing one of the four directions (up, down, left, or right). The starting position and direction can be chosen freely by E869120.

After that, E869120 repeats the following operation:

• After picking up the coin at the current position, the robot rotates 90 degrees to the left or right, and then jumps to the next coin position in the direction it is facing, moving one or more cells.

Can E869120 collect all the coins by choosing the starting position, direction, jump positions, and rotation directions wisely?

Input Format

The input is given from the standard input in the following format:

$ H $ $ W $ $ S_{1, 1}S_{1, 2}S_{1, 3}...S_{1, W} $ $ S_{2, 1}S_{2, 2}S_{2, 3}...S_{2, W} $ : : : $ S_{H, 1}S_{H, 2}S_{H, 3}...S_{H, W} $

Output Format

If there is a way to collect all the coins, output Possible. If it is impossible to collect all the coins no matter what actions are taken, output Impossible.

Sample Input and Output

Sample Input #1

5 5
xooxx
xoxxo
xxoox
ooxoo
xoxxx

Sample Output #1

Possible

Sample Input #2

2 9
oxxxxoxxo
oxoxxoxxo

Sample Output #2

Possible

Sample Input #3

9 25
xxxxxxxxxxxxxxxxxxxxxxxxx
xxoooxxxoooxxooooxxxoooxx
xoxxxoxoxxxoxoxxxoxoxxxox
xoxxxxxoxxxoxoxxxoxoxxxxx
xxoooxxxoooxxooooxxoxxxxx
xxxxxoxoxxxoxoxxxxxoxxxxx
xoxxxoxoxxxoxoxxxxxoxxxox
xxoooxxxoooxxoxxxxxxoooxx
xxxxxxxxxxxxxxxxxxxxxxxxx

Sample Output #3

Impossible

Sample Input #4

6 6
oxxxxo
xoooxx
xoooox
xoooox
xxooxx
oxxxxo

Sample Output #4

Impossible

Notes/Hints

Constraints

• $2 \leq H \leq 100$
• $2 \leq W \leq 100$
• $ S_{i, j} $ is either o or x
• There is at least one coin on the board

Partial Points

This problem is divided into several sub-tasks, and you are considered to have solved a sub-task if you correctly answer all test cases in that sub-task. The score of your submission is the sum of the points of the sub-tasks you solved.

1. (100 points): $N \leq 8$
2. (110 points): $N \leq 16$
3. (150 points): $ H = 2 $
4. (440 points): No additional constraints.

Here, $ N $ is the number of coins on the grid.

Sample Explanation 1

All coins can be collected by moving the robot in the following order.

Sample Explanation 2

All coins can be collected by moving the robot in the following order.

Sample Explanation 3

No matter how the robot is moved, it is impossible to collect all the coins.

Sample Explanation 4

In this case, no matter how the robot is moved, it is impossible to collect all the coins.

见题面 Input 部分

见题面 Output 部分