28218번 - 격자 게임 서브태스크

문제

한국이와 정올이는 격자 모양의 보드에서 한국이부터 차례로 번갈아가며 말을 움직이는 게임을 한다. 자신의 차례를 건너뛸 수 없다.

보드는 $N$개의 행과 $M$개의 열로 이루어져 있으며, 보드의 일부 칸은 막혀 있다. 막혀 있는 칸으로는 말을 움직일 수 없다. 편의상 보드의 (위에서 부터) $i$번째 행과 (왼쪽에서 부터) $j$번째 열이 만나는 지점에 위치한 칸을 $(i, j)$로 표기하자.

말은 한 번에 아래로 한 칸, 오른쪽으로 한 칸 또는 오른쪽 아래 대각선 방향으로 1ドル,ドル 2ドル,ドル $\cdots,ドル $K$칸 움직일 수 있다. (단, 보드의 밖이나 막혀 있는 칸으로 움직일 수는 없으며, $K = 0$인 경우에는 대각선 방향으로 움직일 수 없다.)

말을 움직이는 규칙과 관련한 몇 가지 예시를 살펴보자.

예를 들어, $N = 6,ドル $M = 8,ドル $K = 3$이고 막혀 있는 칸이 없는 보드를 생각하자. $(2, 3)$에 놓인 말이 움직일 수 있는 칸은 총 5ドル$개로 다음 그림에 O 표시된 것과 같다.

위의 상황에서 $(2, 4)$와 $(4, 5)$가 막혀 있다고 가정하자. 이 경우에 $(2, 3)$에 놓인 말이 움직일 수 있는 칸은 총 3ドル$개로 다음 그림에 O 표시된 것과 같다.

다음 그림과 같이 $N = 6,ドル $M = 8,ドル $K = 3$이고 막혀 있는 칸이 없는 보드를 생각하자. 이 보드에서 $(5, 7)$에 놓인 말이 움직일 수 있는 칸은 총 3ドル$개로 다음 그림에 O 표시된 것과 같다.

마지막으로, 다음 그림과 같이 $N = 6,ドル $M = 8,ドル $K = 0$이고 막혀 있는 칸이 없는 보드를 생각하자. 이 보드에서 $(1, 1)$에 놓인 말이 움직일 수 있는 칸은 총 2ドル$개로 다음 그림에 O 표시된 것과 같다.

게임의 목표는 말을 보드의 맨 오른쪽 아래 칸, 즉, $(N, M)$으로 옮기는 것이고, 마지막으로 말을 움직인 사람이 이긴다. 한국이와 정올이 모두 최선을 다해 게임에 임한다고 가정하자.

게임을 시작하는 위치(초기에 말이 놓여 있는 위치)에 따라 게임의 승자가 달라질 수 있다. $Q$개의 보드 상의 위치 $(x_1, y_1),ドル $(x_2, y_2),ドル $\cdots,ドル $(x_Q, y_Q)$가 주어질 때 각 위치에서 게임을 시작할 때의 승자를 구하여라.

입력

첫 번째 줄에 세 정수 $N,ドル $M,ドル $K$가 공백을 사이에 두고 주어진다.

이후 $N$개의 줄에 걸쳐 #과 .으로만 구성된 길이 $M$의 문자열이 한 줄에 하나씩 주어진다. 1ドル ≤ i ≤ N$ 과 1ドル ≤ j ≤ M$에 대해, $i$번째 줄의 $j$번째 문자가 ‘#’ 이면 $(i, j)$가 막혀 있는 칸임을, ‘.’이면 막혀 있지 않은 칸임을 의미한다.

그 다음 줄에 정수 $Q$가 주어진다.

다음 $Q$개의 줄 중 $i$ (1ドル ≤ i ≤ Q$)번째 줄에는 정수 $x_i$와 $y_i$가 공백을 사이에 두고 주어진다.

출력

주어지는 $Q$개의 각 위치마다 한국이가 이긴다면 First를 정올이가 이긴다면 Second를 한 줄에 하나씩 순서대로 출력하라.

제한

• 2ドル ≤ N ≤ 300$
• 2ドル ≤ M ≤ 300$
• $K ≥ 0$
• $K ≤ N - 1$
• $K ≤ M - 1$
• $(N, M)$ 칸은 막혀 있지 않다.
• 임의의 막혀 있지 않은 칸에서 시작해서 말을 규칙에 따라 $(N, M)$으로 옮길 수 있다.
• 1ドル ≤ Q ≤ 300$
• 모든 $i$ (1ドル ≤ i ≤ Q$)에 대해:
  • 1ドル ≤ x_i ≤ N,ドル 1ドル ≤ y_i ≤ M$
  • $(x_i , y_i)$ 칸은 막혀 있지 않다.
  • $(x_i , y_i)$는 $(N, M)$이 아니다.

서브태스크

힌트