로봇 경주

바이트랜드에서 미로 로봇 경주가 열린다. 미로는 직사각형 모양이고, $n$개의 행과 $m$개의 열로 배열된 $n \times m$개의 칸으로 나뉜다. 각 칸은 빈 칸이거나 장애물이 놓인 칸이다.

참가자는 경주에 로봇을 등록하고 한 명씩 차례로 미로 앞에 온다. 참가자마다 시작 칸과 목표 칸의 좌표를 무작위로 받는다. 로봇을 시작 칸에 놓고, 여러 번 이동해서 목표 칸까지 보내야 한다.

경기를 더 어렵게 만들려고 규칙은 이동 방향을 제한한다. 로봇은 한 번 이동할 때 오른쪽으로 한 칸 또는 아래로 한 칸만 움직일 수 있다. 다른 방향으로 로봇을 움직이는 것은 허용하지 않는다.

시작 칸에서 목표 칸까지 로봇을 가장 빨리 보낸 참가자가 우승한다. 제한 시간 안에 로봇이 목표 칸에 도착하지 못하면 그 참가자는 실격된다.

주최 측은 참가자가 좌표를 잘못 받으면 어떻게 움직여도 로봇이 목표 칸에 도착하지 못한다는 사실을 알아차렸다. 그런 경우에는 참가자에게 좌표를 새로 준다.

크기가 $n \times m$인 미로의 지도와 시작 칸, 목표 칸의 좌표 쌍 $q$개가 주어진다. 각 좌표 쌍에 대해 오른쪽 또는 아래로 가는 이동만으로 시작 칸에서 목표 칸까지 갈 수 있는지 판단하시오.

첫째 줄에 세 정수 $n$, $m$, $q$가 주어진다. 각각 미로의 행 개수, 미로의 열 개수, 좌표 쌍의 개수이다.

다음 $n$개의 줄에는 미로의 칸을 나타내는 문자가 각각 $m$개씩 주어진다. 문자 .은 빈 칸이고, 문자 #은 장애물이 있는 칸이다.

이어서 좌표 쌍을 나타내는 $q$개의 줄이 주어진다. 그중 $i$번째 줄에는 네 정수 $r_{1,i}$, $c_{1,i}$, $r_{2,i}$, $c_{2,i}$가 주어진다. 순서대로 시작 칸의 행과 열, 목표 칸의 행과 열이다.

• $1 \leq n, m \leq 1000$이고 $1 \leq q \leq 10^6$이다.
• 모든 $i \in \{1, 2, \ldots, q\}$에 대해 $1 \leq r_{1,i}, r_{2,i} \leq n$이고 $1 \leq c_{1,i}, c_{2,i} \leq m$이다.
• 모든 $i \in \{1, 2, \ldots, q\}$에 대해 미로에서 좌표가 $(r_{1,i}, c_{1,i})$인 칸과 $(r_{2,i}, c_{2,i})$인 칸은 빈 칸이다.
• 전체 테스트 케이스의 20%에서는 $q \leq 300$이다.

$q$개의 줄을 출력한다. $i$번째 줄에는 $i$번째 시작 칸에서 $i$번째 목표 칸까지 로봇이 갈 수 있으면 YES를, 갈 수 없으면 NO를 출력한다.