406703: GYM102501 L River Game

L. River Gametime limit per test0.5 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output Together with an ornithologist friend, you are spending hours bird-watching in wetlands, waiting for a rare bird that you want to take a picture of.

In order to kill time, you devised a little game. The wetland is represented by an $$$N \times N$$$ grid made of 3 types of squares: firm ground, wet zone, and protected zone.

Connected wet zone squares form wet areas, which are maximal sets of wet zone squares such that we can go from any square of the area to any other square of the area by a path of connected wet zone squares. Two squares are considered connected when they share one edge, so that squares not on the border of the grid are connected to 4 other squares. Each wet area must be connected to both the left and right sides of the grid, and does not contain more than $$$2N$$$ wet zone squares. Two wet zone squares that belong to two different wet areas will always be at distance at least 3 from each other, the distance being counted by moving horizontally or vertically on the grid. For example, in the two examples below, the blue squares are at distance 3 from one another.

One after the other, you and your friend will each take turns placing a camera on the wetland with the following constraints:

• The camera must be on a firm ground square.
• The camera must be adjacent to a wet zone square so that you can take bird photos.
• The camera must not be on a protected zone square.
• There cannot be two cameras on the same square.
• No two cameras adjacent to the same wet area can be adjacent (again, the notion of adjacency means sharing an edge).

The first player who cannot place a camera anymore loses the game. Assuming both players play optimally, will the first player win or lose?

Input

The input consists of the following lines:

• on the first line, the integer $$$N$$$;
• on the next $$$N$$$ lines, a string representing a row of the grid: "*" represents a wet zone square, "." represents a firm ground square and "x" represents a protected square.

Limits

The input satisfies $$$1 \le N \le 10$$$.

Output

The four words "First player will win" if the first player wins the game provided both players play optimally, or "Second player will win" otherwise.

ExamplesInput

3
...
...
***

Output

First player will win

Input

10
**********
*.x.*.....
*...*.....
*****.....
..........
..........
xx******..
***x...*..
..*...x*.x
..********

Output

Second player will win

Note

Sample Explanation 1

The first player can place a camera in three possible places: if he places a camera in the left or right position, then the second player can place one in the other position and wins the game. On the other hand, if the first player places a camera in the middle, the second player cannot place another camera and loses.