cho.sh

Wall Making Game

Two players alternately pick an empty cell and turn its row and column lines into walls until blocked, and the player unable to move loses.

Hard9Game theoryDivide and conquerBrute forceNo attempts yetTime limit2sMemory limit256 MB

Problem

Wall Making Game is a board game for two players who move alternately, and it is popular right now.

The game is played on a board of H×WH \times W cells. Each cell is empty, marked, or a wall. When the game starts the board has no walls.

The two players move alternately as follows.

  1. The player chooses one empty cell. An empty cell is a cell that is neither marked nor a wall. A player with no cell to choose loses.
  2. From the chosen cell the player advances one cell at a time in each of the four directions (up, down, left, right), turning every cell it passes into a wall, and stops in a direction as soon as it reaches a wall or leaves the board. The chosen cell also becomes a wall.

A marked cell cannot be chosen in step 1, but it can be turned into a wall in step 2.

Figure 1 shows a move in which the player chooses the cell in the third row and the fourth column.

Figure 1: one move in Wall Making Game.

Write a program that decides which player wins from the given initial board when both players play optimally.

Input

The first line contains the height HH and the width WW of the board (1≤H,W≤201 \le H, W \le 20).

Each of the next HH lines contains WW characters describing the initial board. The jj-th character of the ii-th line is . if the cell in row ii and column jj is empty, or X if the cell is marked.

Output

Print First on one line if the player who moves first wins. Otherwise print Second.