모두 정사각형이다

어느 날 Little Q가 눈을 떠 보니 2차원 픽셀 세계 안에 있었다. 이 세계는 $n \times m$개의 정사각형 칸으로 이루어진 격자이다. Little Q는 칸의 변을 따라서만 걸을 수 있으므로, 정수 $x$, $y$에 대해 $0 \leq x \leq n$, $0 \leq y \leq m$을 만족하는 점 $(x, y)$에만 머무를 수 있다. 각 칸의 중심에는 수가 적혀 있다. $w_{i,j}$ ($1 \leq i \leq n$, $1 \leq j \leq m$)는 점 $(i-0.5, j-0.5)$에 적힌 수이다.

Little Q는 픽셀 세계를 빠져나갈 방법을 몰라 그냥 돌아다녔다. 질의 $q$개가 주어진다. 각 질의는 정수 $(x, y)$와, Little Q의 경로를 나타내는 문자열 $S$로 이루어진다. 처음에 Little Q는 $(x, y)$에 서 있다. 그다음 $S_1, S_2, \dots, S_{|S|}$의 이동을 차례로 한 번씩 수행한다. 이동은 다음과 같다.

• L: $(x, y)$에서 $(x-1, y)$로 이동한다.
• R: $(x, y)$에서 $(x+1, y)$로 이동한다.
• D: $(x, y)$에서 $(x, y-1)$로 이동한다.
• U: $(x, y)$에서 $(x, y+1)$로 이동한다.

Little Q가 픽셀 세계 밖으로 나가는 일은 없고, 경로는 단순 다각형을 이룬다고 보장된다. 각 질의마다 경로가 이루는 다각형 안에 있는 서로 다른 수가 몇 개인지 구하라.

다행히 이 문제를 풀고 나자 Little Q는 자기 침대에서 깨어났다. 픽셀 세계는 꿈이었다!

첫 줄에 테스트 케이스 수 $T$ ($1 \leq T \leq 10$)가 주어진다. 각 테스트 케이스는 다음과 같다.

첫 줄에 세 정수 $n$, $m$, $q$ ($1 \leq n, m \leq 400$, $1 \leq q \leq 200\,000$)가 주어진다. 각각 픽셀 세계의 크기와 질의의 수이다.

다음 $n$개의 줄에는 각각 $m$개의 정수가 주어진다. $i$번째 줄에는 $w_{i,1}, w_{i,2}, \dots, w_{i,m}$ ($1 \leq w_{i,j} \leq n \times m$)이 주어진다. "U"가 실제로 위를 뜻하도록 하려면 이 표를 회전해서 읽어야 한다는 점에 유의하라.

다음 $q$개의 줄에는 각각 정수 $x$, $y$ ($0 \leq x \leq n$, $0 \leq y \leq m$)와 비어 있지 않은 문자열 $S$ ($S_i \in \{`L`, `R`, `D`, `U`\}$)가 주어진다. 이 문자열은 해당 질의의 경로를 나타낸다.

모든 테스트 케이스에 걸친 $|S|$의 총합은 4,000,000 이하이다.

각 질의마다 한 줄에 정수 하나를 출력한다. 그 정수는 다각형 안에 있는 서로 다른 수의 개수이다.