백룸

마법사 Harry는 빵 굽기를 좋아한다. 어느 날, 그는 자신을 ``백룸''으로 이동시킬 수 있는 주문을 발견했고(이 말장난은 스웨덴어에서만 통한다), 기쁨에 넘쳤다. 그러나 그 주문을 사용했을 때 그는 빵집으로 이동한 것이 아니라 무한히 큰 격자로 이동했다. 격자의 각 칸은 비어 있거나 막혀 있다. 격자에서는 위, 아래, 왼쪽 또는 오른쪽에 인접한 막히지 않은 칸으로 이동할 수 있다. 한동안 돌아다닌 뒤, 그는 막힌 칸의 패턴이 주기적이라는 것을 알아차린다. 더 정확히 말하면, 무한히 반복되는 $R \times C$ 패턴이 있다. 이것이 정확히 어떻게 작동하는지는 아래 그림을 참고하라.

예제 1의 시각화. 기본 패턴은 빨간색으로 표시되어 있다. $(0,0)$은 막혀 있지 않지만, $(1,1)$은 막혀 있다. 첫 번째 질문의 좌표는 $(2,4)$와 $(4,3)$에 표시되어 있다. 물론 격자는 그림에 표시된 범위를 넘어 무한히 이어진다.

탈출하려면 그는 격자의 특정 칸에 도달해야 한다. 하지만 그의 순간이동 마법은 조금 녹슬었으므로, 다음과 같은 형식의 질문을 당신에게 $Q$개 할 것이다. ``내가 $(s_x, s_y)$ 칸으로 순간이동한다면, $(g_x, g_y)$ 칸까지 걸어갈 수 있는가?''

채점

여러 테스트 그룹으로 이루어진 테스트 세트로 풀이를 평가한다. 한 그룹의 점수를 얻으려면 그 그룹의 모든 테스트 케이스를 통과해야 한다.

그룹 | 점수 | 제한 조건

$1$ | $7$ | $R, C \leq 2$, $Q \leq 5$, $s_x, s_y, g_x, g_y \leq 500$

$2$ | $4$ | $R, C, Q \leq 5$, $s_x, s_y, g_x, g_y \leq 500$

$3$ | $8$ | $R, C, Q \leq 5$, $s_x, s_y, g_x, g_y \leq 10^5$

$4$ | $25$ | $R, C, Q \leq 5$

$5$ | $15$ | $R, C \leq 5$

$6$ | $21$ | $R, C \leq 25$

$7$ | $20$ | 추가 제한 조건이 없다.

첫 번째 줄에 격자의 행과 열의 수를 나타내는 두 정수 $R$와 $C$ ($1 \leq R,C \leq 1000$)가 주어진다.

다음 $R$개의 줄에는 각각 .`''와 #'' 문자로 이루어진 길이 $C$의 문자열이 주어진다. 이 문자열들은 격자의 행이다. 문자 ```#''는 해당 칸이 막혀 있음을 의미하고, ```.`''는 해당 칸이 비어 있음을 의미한다.

그다음 줄에는 답해야 하는 질문의 수인 정수 $Q$ ($1 \leq Q \leq 10^5$)가 주어진다.

이어지는 $Q$개의 줄에는 각각 질문의 좌표를 나타내는 네 정수 $s_x, s_y, g_x, g_y$ ($0 \leq s_x, s_y, g_x, g_y \leq 10^{12}$)가 주어진다. 이 좌표에 있는 두 칸 중 어느 것도 막혀 있지 않음이 보장된다.

각 질문마다 Harry가 $(s_x, s_y)$ 칸에서 $(g_x, g_y)$ 칸까지 걸어갈 수 있다면 Yes`''를, 그렇지 않으면 No`''를 출력한다.

• 질문 1: Harry는 $(2,4)$에서 출발하여 $(4,3)$로 이동하려 한다. 이를 위해 오른쪽, 아래쪽, 오른쪽으로 이동할 수 있다.

• 질문 2: 시작점과 도착점이 벽으로 분리되어 있으므로 답은 ```No`''이다.

• 질문 3: Harry는 이미 도착점에서 출발하므로 즉시 끝난다.

• 질문 4: 아주 멀리 나가더라도 격자는 계속 이어진다. 답은 ```Yes`''인 것으로 밝혀진다.

• 질문 5: 이번에도 시작점과 도착점이 벽으로 분리되어 있다.