Maze

Time limit2sMemory limit1024 MB

Summary

Given a grid where each cell forbids one direction, count the cells that lie on some walk from each query's start cell to its end cell, or print 0 if the end is unreachable.

Level: Hard8 of 10
Topics: Graph, Topological sort, DFS
Solved: No attempts yet

Problem

Minje runs a maze game room. The maze is a grid of $N$ rows and $M$ columns, and each cell has one of four directions written on it: up, down, left, or right. A participant can move in four directions, but cannot move in the direction written on the current cell or in a direction that leaves the maze.

Every time a participant enters the maze and comes back out, Minje cleans the whole maze. Cleaning all $N \times M$ cells each time exhausted him. Minje realized that cells no participant walked through need not be cleaned, so from now on he only cleans cells that a participant might have passed through.

Given the start and end cell of each participant's exploration, write a program that finds the number of cells Minje has to clean.

Input

The first line contains the maze size $N$ , $M$ ( $1 \le N, M \le 1,000$ ) and the number of queries $Q$ ( $1 \le Q \le 300,000$ ). The next $N$ lines each contain $M$ characters describing the maze. Each character is one of U, D, L, R, meaning that the participant cannot move up, down, left, or right from that cell, respectively.

The next $Q$ lines each contain the row and column of the start cell, followed by the row and column of the end cell. The start and end cells can be the same. A participant can keep exploring the maze after first reaching the end cell.

Output

Print $Q$ lines, one answer per query. Print 0 if the end cell cannot be reached from the start cell. Otherwise, print the number of cells Minje has to clean.

Examples1

Example 1

Input

5 5 5
DDDDD
RDDDL
RRDLL
RUUUL
UUUUU
1 1 5 5
2 2 5 5
3 3 5 5
4 4 5 5
5 5 5 5

Expected output