미로

민제는 미로 게임장을 운영하고 있다. 미로는 $N$행 $M$열 격자이고, 각 칸에는 상, 하, 좌, 우 네 방향 중 하나가 적혀 있다. 참가자는 네 방향으로 이동할 수 있지만, 자신이 있는 칸에 적힌 방향이나 미로 밖으로 나가는 방향으로는 이동할 수 없다.

참가자가 미로에 한 번 들어갔다 나올 때마다 민제는 미로 전체를 청소한다. 매번 $N \times M$개의 칸을 모두 청소하다가 민제는 골병이 들고 말았다. 참가자가 돌아다니지 않은 칸은 청소할 필요가 없다는 것을 깨달은 민제는, 앞으로 참가자가 지나갔을 가능성이 있는 칸만 청소하기로 했다.

각 참가자가 탐험을 시작한 위치와 끝낸 위치가 주어질 때, 민제가 청소해야 할 칸의 수를 구하는 프로그램을 작성하여라.

첫 번째 줄에는 미로의 크기 $N$, $M$ ($1 \le N, M \le 1,000$)과 쿼리의 수 $Q$ ($1 \le Q \le 300,000$)가 주어진다. 다음 $N$개의 줄에는 미로의 형태에 해당하는 $M$개의 문자가 주어진다. 각 문자는 U, D, L, R 중 하나이며, 이는 해당 칸에서 각각 위, 아래, 왼쪽, 오른쪽으로 이동할 수 없음을 뜻한다.

그다음 $Q$개의 줄에는 시작점의 행 번호와 열 번호, 도착점의 행 번호와 열 번호가 주어진다. 시작점과 도착점은 같을 수 있다. 참가자는 도착점에 처음 도달한 뒤에도 미로 탐험을 계속할 수 있다.

$Q$개의 줄에 걸쳐 각 줄에 쿼리에 대한 답을 출력한다. 시작점에서 도착점까지 이동할 수 없으면 0을 출력하고, 그렇지 않으면 민제가 청소해야 할 칸의 수를 출력한다.