It's All Squares

Problem Description

One day when Little Q woke up, he found himself being inside a 2D pixel world. The world is a grid with $n\times m$ square cells. Little Q can only walk along the side of these cells, which means he can stay at a point $(x,y)$ if and only if $0\leq x\leq n$ and $0\leq y\leq m$, where $x$ and $y$ are all integers. There is a number written at the center of each cell, number $w_{i,j}$ ($1\leq i\leq n,1\leq j\leq m$) is written at the point $(i-0.5,j-0.5)$. Little Q had no idea about how to escape from the pixel world, so he started wandering. You will be given $q$ queries, each query consists of two integers $(x,y)$ and a string $S$, denoting the route of Little Q. Initially, Little Q will stand at $(x,y)$, then he will do $|S|$ steps of movements $S_1,S_2,\dots,S_{|S|}$ one by one. Here is what he will do for each type of movement: · "$\texttt{L}$" : Move from $(x,y)$ to $(x-1,y)$. · "$\texttt{R}$" : Move from $(x,y)$ to $(x+1,y)$. · "$\texttt{D}$" : Move from $(x,y)$ to $(x,y-1)$. · "$\texttt{U}$" : Move from $(x,y)$ to $(x,y+1)$. It is guaranteed that Little Q will never walk outside of the pixel world, and the route will form a simple polygon. For each query, please tell Little Q how many distinct numbers there are inside the polygon formed by the route. Fortunately, after solving this problem, Little Q woke up on his bed. The pixel world had just been a dream!

Input

The first line of the input contains a single integer $T$ ($1 \leq T \leq 10$), the number of test cases. For each case, the first line of the input contains three integers $n,m$ and $q$ ($1 \leq n,m \leq 400$, $1\leq q\leq 200\,000$), denoting the size of the pixel world and the number of queries. Each of the following $n$ lines contains $m$ integers, the $i$-th line contains $m$ integers $w_{i,1},w_{i,2},\dots,w_{i,m}$ ($1\leq w_{i,j}\leq n\times m$), denoting the number written in each cell. Each of the following $q$ lines contains two integers $x,y$ ($0\leq x\leq n$, $0\leq y\leq m$) and a non-empty string $S$ ($S_i\in\{\texttt{L},\texttt{R},\texttt{D},\texttt{U}\}$), denoting each query. It is guaranteed that $\sum |S|\leq 4\,000\,000$.

Output

For each query, output a single line containing an integer, the number of distinct numbers inside the polygon.

Sample Input

1
3 3 2
1 2 3
1 1 2
7 8 9
0 0 RRRUUULLLDDD
0 0 RRUULLDD

Sample Output

6
2

Source

2020 Multi-University Training Contest 2