#P7782. It's All Squares

It's All Squares

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×mn\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)(x,y) if and only if 0≤x≤n0\leq x\leq n and 0≤y≤m0\leq y\leq m, where xx and yy are all integers. There is a number written at the center of each cell, number wi,jw_{i,j} (1≤i≤n,1≤j≤m1\leq i\leq n,1\leq j\leq m) is written at the point (i−0.5,j−0.5)(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 qq queries, each query consists of two integers (x,y)(x,y) and a string SS, denoting the route of Little Q. Initially, Little Q will stand at (x,y)(x,y), then he will do ∣S∣|S| steps of movements S1,S2,…,S∣S∣S_1,S_2,\dots,S_{|S|} one by one. Here is what he will do for each type of movement: · "L\texttt{L}" : Move from (x,y)(x,y) to (x−1,y)(x-1,y). · "R\texttt{R}" : Move from (x,y)(x,y) to (x+1,y)(x+1,y). · "D\texttt{D}" : Move from (x,y)(x,y) to (x,y−1)(x,y-1). · "U\texttt{U}" : Move from (x,y)(x,y) to (x,y+1)(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 TT (1≤T≤101 \leq T \leq 10), the number of test cases. For each case, the first line of the input contains three integers n,mn,m and qq (1≤n,m≤4001 \leq n,m \leq 400, 1≤q≤200 0001\leq q\leq 200\,000), denoting the size of the pixel world and the number of queries. Each of the following nn lines contains mm integers, the ii-th line contains mm integers wi,1,wi,2,…,wi,mw_{i,1},w_{i,2},\dots,w_{i,m} (1≤wi,j≤n×m1\leq w_{i,j}\leq n\times m), denoting the number written in each cell. Each of the following qq lines contains two integers x,yx,y (0≤x≤n0\leq x\leq n, 0≤y≤m0\leq y\leq m) and a non-empty string SS ($S_i\in\{\texttt{L},\texttt{R},\texttt{D},\texttt{U}\}$), denoting each query. It is guaranteed that ∑∣S∣≤4 000 000\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