Minh just invented a robot that can recognize instructions on the floor and move according to the instructions. The floor is a grid with R rows and C columns. The rows are numbered 1 to R from top to bottom, the columns are numbered 1 to C from left to right. A cell on row u (1 <= u <= R) and column v (1 <= v <= C) is called cell (u, v). Each cell of the grid has the instruction for the next move of the robot.
Example: [insert image]
- The robot is initially at (1, 1), on the next move the robot moves to (1, 2).
- At (1, 2), the robot receives the instruction to move down to (2, 2).
- At (2, 2), the robot receives the instruction to move down to (3, 2).
- At (3, 2), the robot receives the instruction to move up to (2, 2).
- The robot keeps moving between (2, 2) and (3, 2) infinitely.
Minh wants to make the robot move from cell (xs, ys) to cell (xt, yt) but the instructions can prevent the robot from moving to the desired destination. You can change the instructions of some cells to make the robot move from (xs, ys) to (xt, yt). Your task is to choose the minimum number of cells to change the instructions. If there are many ways to change the instructions with the minimum number of cells, count the number of ways.
Input: First line contains R, C and q, where R is the number of rows, C is the number of columns and q is the number of queries.
R lines follow. Each line contains a string with length C. The $$$v$$$th character on line $$$u$$$ represents the instruction on cell (u, v). The instruction can be one of the characters U, D, L and R. U means up, D means down, L means left and R means right.
q lines follow. Each line contains four integers xs, ys, xt and yt.
Output: Print q lines. Each line contains two integers separated by a space. The first number is the minimum number of cells, the second way is the number of ways mod 1000000007.
Constraints: R * C <= 10^6, q <= 10.
Sample: Input: 3 4 2 RDRD RDRD UUUL 1 1 3 2 1 1 3 4 Output: 0 1
Input: 2 2 1 UD RR 1 1 2 2 Output: 1 2