Solitaire of the stones (1) P39965

Consider a solitaire consisting of a board n × n, where every square is empty or has a stone. The only movement allowed consists of jumping over a neighboring stone (horizontally or vertically), leaving the moved stone in the following position, which has to be empty before the jump. The stone that has been jumped is removed from the board. (It is like the movement of killing a piece in checkers, but with horizontal or vertical jumps instead of diagonal jumps.) The goal of the solitaire is to end with a only stone in the board.

Write a program that prints if a given solitaire has solution or not. If it has, it must print if it is possible that the stone remains at the position of the middle; in this case we will say that it has a nice solution.

Input

Input consists of an odd natural n ≥ 3, followed by n rows with n characters each one. A ’X’ indicates a stone. The empty positions are indicated with a dot.

Output

Your program must print "it has nice solution", "it has solution" or "it does not have solution" as required.