407692: GYM102875 F Flee from Maze

Little Rabbit is trapped in a maze, which can be represented as a grid with $$$n$$$ rows and $$$m$$$ columns. Some blocks of the maze are empty lands, and some are walls. Little Rabbit can only step on empty lands. He cannot step on walls or outside the maze.

Not knowing where to go, Little Rabbit decides to follow a fixed pattern. The pattern is given as a string $$$s$$$ of length $$$l$$$, which contains only L, R, D and U. We use $$$(x,y)$$$ to represent a block in the $$$x$$$-th row and the $$$y$$$-th column. The meanings of L, R, D and U are as follows.

• L: Move from $$$(x,y)$$$ to $$$(x,y-1)$$$.
• R: Move from $$$(x,y)$$$ to $$$(x,y+1)$$$.
• D: Move from $$$(x,y)$$$ to $$$(x+1,y)$$$.
• U: Move from $$$(x,y)$$$ to $$$(x-1,y)$$$.

Given a certain maze and a certain pattern $$$s$$$, there are $$$q$$$ queries. In each query, $$$x_1,y_1,z,x_2,y_2,a,b$$$ are given. In the beginning, Little Rabbit is located at $$$(x_1,y_1)$$$. Little Rabbit will start from $$$s_z$$$, and follow the pattern cyclically and infinitely as $$$s_z,s_{z+1},\cdots,s_l,s_1,s_2,\cdots,s_l,s_1,s_2,\cdots$$$. If a movement is invalid (such as moving into a wall or outside the maze), he will just stay at the current position, which is also considered as a step. You need to tell Little Rabbit the number of integers $$$u$$$ in $$$[a, b]$$$, such that he is located at $$$(x_2, y_2)$$$ after the $$$u$$$-th step. As a special case, it is considered that he is located at $$$(x_1, y_1)$$$ after the $$$0$$$-th step.

The first line of the input contains an integer $$$T$$$ $$$(1 \le T \le 10)$$$ — the number of test cases.

The first line of each test case contains three integers $$$n,m,q$$$ $$$(1 \le n,m \le 30, 1 \le q \le 3\cdot 10^5)$$$ — the number of rows, columns and queries.

Then in the next $$$n$$$ lines, each line contains a string of length $$$m$$$, which contains only . and *. If the $$$y$$$-th character of the $$$x$$$-th string is *, the block $$$(x,y)$$$ is a wall. Otherwise, the block $$$(x,y)$$$ is an empty land.

Then the next line contains a string of length $$$l$$$ $$$(1 \le l \le 5000)$$$, which contains only L, R, D and U, indicating the fixed pattern.

Then in the next $$$q$$$ lines, each line contains seven integers $$$x_1,y_1,z,x_2,y_2,a,b$$$ $$$(1 \le x_1,x_2 \le n$$$, $$$1 \le y_1,y_2 \le m$$$, $$$1 \le z \le l$$$, $$$0 \le a\le b \le 10^9)$$$, indicating a query.

The output of the $$$x$$$-th test case begins with Case #x: in a single line.

Then in the next $$$q$$$ lines, the $$$i$$$-th line contains an integer indicating the answer of the $$$i$$$-th query.

1
3 3 3
...
.*.
...
RRDDLLUU
1 1 1 3 3 1 1000
1 1 1 3 3 4 4
3 3 1 1 1 1 1000

Case #1:
125
1
125