Grid Game

Hanguk and Jeongol play a game on a grid board. Hanguk moves first, and the two players take turns moving a piece. Neither player may skip a turn.

The board has $N$ rows and $M$ columns, and some cells are blocked. The piece cannot move into a blocked cell. For convenience, the cell where the $i$-th row (counting from the top) meets the $j$-th column (counting from the left) is written as $(i, j)$.

In one move, the piece moves down by one cell, right by one cell, or diagonally down and right by $1$, $2$, $\cdots$, $K$ cells. (The piece cannot move outside the board or into a blocked cell. If $K = 0$, the piece cannot move diagonally.)

Here are a few examples of the movement rules.

For example, take $N = 6$, $M = 8$, $K = 3$, and a board with no blocked cells. A piece at $(2, 3)$ can move to 5 cells, marked with O in the figure below.

Now suppose $(2, 4)$ and $(4, 5)$ are blocked. Then the piece at $(2, 3)$ can move to 3 cells, marked with O in the figure below.

In the next figure, $N = 6$, $M = 8$, $K = 3$, and no cells are blocked. A piece at $(5, 7)$ can move to 3 cells, marked with O.

Finally, take $N = 6$, $M = 8$, $K = 0$, and no blocked cells. A piece at $(1, 1)$ can move to 2 cells, marked with O.

The goal is to move the piece to the bottom-right cell $(N, M)$. The player who makes the last move wins. Both players play optimally.

The winner can depend on the starting position. You are given $Q$ positions $(x_1, y_1), (x_2, y_2), \cdots, (x_Q, y_Q)$ on the board. For each position, find the winner when the game starts there.

The first line contains three integers $N$, $M$, and $K$, separated by spaces.

The next $N$ lines each contain a string of length $M$ made only of # and .. If the $j$-th character of the $i$-th line is #, cell $(i, j)$ is blocked. If it is ., the cell is not blocked.

The next line contains an integer $Q$.

Each of the next $Q$ lines contains two integers $x_i$ and $y_i$, separated by a space.

For each of the $Q$ positions, print First if Hanguk wins, or Second if Jeongol wins. Print one result per line, in order.

• $2 \le N \le 300$
• $2 \le M \le 300$
• $K \ge 0$
• $K \le N - 1$
• $K \le M - 1$
• Cell $(N, M)$ is not blocked.
• From any unblocked cell, the piece can reach $(N, M)$ by following the movement rules.
• $1 \le Q \le 300$
• For every $i$ ($1 \le i \le Q$):
  • $1 \le x_i \le N$, $1 \le y_i \le M$
  • Cell $(x_i, y_i)$ is not blocked.
  • $(x_i, y_i)$ is not $(N, M)$.