벽 만들기 게임

빈 칸을 번갈아 골라 네 방향으로 막힐 때까지 벽을 세우며 더 이상 둘 곳이 없는 쪽이 패배합니다.

어려움9게임 이론분할 정복완전 탐색아직 제출이 없습니다시간 제한2초메모리 제한256 MB

문제

벽 만들기 게임은 두 사람이 번갈아 두는 보드게임이고, 요즘 유행이다.

게임은 H×WH \times W 크기의 판에서 진행한다. 판의 각 칸은 빈 칸, 표시된 칸, 벽 중 하나다. 게임을 시작할 때 판에는 벽이 하나도 없다.

두 사람은 다음과 같이 번갈아 한 번씩 움직인다.

  1. 빈 칸을 하나 고른다. 빈 칸은 표시된 칸도 아니고 벽도 아닌 칸이다. 고를 칸이 없으면 그 사람이 진다.
  2. 고른 칸에서 위, 아래, 왼쪽, 오른쪽 네 방향으로 각각 한 칸씩 나아가면서 지나간 칸을 모두 벽으로 바꾸고, 벽에 닿거나 판 밖으로 나가게 되면 그 방향을 멈춘다. 고른 칸도 벽으로 바뀐다.

표시된 칸은 1번에서 고를 수 없지만, 2번에서 벽으로 바뀔 수는 있다.

그림 1은 셋째 행 넷째 열의 칸을 고른 움직임의 예다.

그림 1: 벽 만들기 게임에서 한 번 움직인 예.

두 사람이 모두 최선을 다해 둘 때 주어진 처음 판에서 누가 이기는지 판정하는 프로그램을 작성하시오.

입력

첫째 줄에 판의 세로 길이 HH와 가로 길이 WW가 주어진다 (1H,W201 \le H, W \le 20).

다음 HH개의 줄에 처음 판의 상태가 주어진다. 각 줄은 WW개의 문자로 이루어진다. ii번째 줄의 jj번째 문자는 iijj열의 칸이 빈 칸이면 ., 표시된 칸이면 X다.

출력

먼저 두는 사람이 이기면 First를, 그렇지 않으면 Second를 한 줄에 출력한다.