미로

민제는 미로 게임장을 운영하고 있다. 게임장에 있는 미로는 N행 M열 크기의 격자 모양이고, 각 칸에는 상, 하, 좌, 우 네 방향 중 하나가 쓰여 있다. 미로 안을 돌아다닐 때는 네 방향으로 이동할 수 있으나, 자신이 위치한 칸에 적혀 있는 방향이나 미로를 벗어나는 방향으로는 이동할 수 없다.

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

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

첫 번째 줄에는 미로의 크기 N, M (1 ≤ N, M ≤ 1,000), 쿼리의 수 Q (1 ≤ Q ≤ 300,000)가 주어진다.

두 번째 줄에는 N개의 줄에는 미로의 형태에 해당하는 M개의 문자가 주어진다. 각 문자는 U, D, L, R 중 하나이며 이는 미로의 해당 칸에서 각각 위, 아래, 왼쪽, 오른쪽으로 이동할 수 없음을 의미한다.

N+2번째 줄부터 Q개의 줄에는 시작점의 행 번호와 열 번호, 도착점의 행 번호와 열 번호가 주어진다. 시작점과 도착점이 같을 수 있으며 참가자가 도착점에 처음 도달한 다음에도 미로 탐험을 계속할 수 있음에 유의하여라.

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