OpenKattis
National University of Singapore

Xortris

/problems/xortris/file/statement/en/img-0001.png
Screenshot of World of Xor

It is 1990 and you are in the development team of a video game that is going to revolutionize the future of arcades. The player is given a rectangular board with some white and black squares. The goal is to turn the whole board white. At each turn, the player may choose a tetromino from an infinite supply, move and rotate it within the limits of the board, and toggle the colour of the four squares covered by the tetromino. A tetromino is a connected set of 4 squares (see Figure 1).

Unfortunately, the testing team has been complaining about some levels being impossible to solve. You know that testers are skilled enough to place a piece in any position and rotation needed, so the problem may be somewhere else. Your next debugging step is to write a program that checks whether a level is solvable.

\includegraphics[width=0.5\textwidth ]{Tetrominoes_IJLO_STZ_Worlds}
Figure 1: All tetrominoes. From Wikimedia.

Input

The first line contains two integers $m$ and $n$ ($1 \leq m,n \leq 100$), the dimensions of the board. $m$ lines with $n$ characters each follow. The character ‘.’ represents a white square, and the character ‘X’ represents a black square.

Output

One line with the word “possible” if the level is solvable and “impossible” if it is not.

Sample Input 1 Sample Output 1
3 3
...
...
...
possible
Sample Input 2 Sample Output 2
3 3
XXX
XXX
XXX
impossible