Truck Route Validator

You are given a rectangular grid with M rows (streets) and N columns (avenues). A truck starts at a given intersection and follows a series of moves represented by the characters \(U\) (up), \(D\) (down), \(L\) (left) and \(R\) (right). The moves are executed one by one.

The route is considered valid if and only if:

• The truck does not leave the grid boundaries.
• The truck does not revisit any intersection (i.e. no intersection is visited more than once).

Note that the starting position is provided in 1-indexed format but you should convert it into 0-indexed format internally.

You need to process multiple test cases. For each test case, you are provided with the grid dimensions and a sequence of routes. For each route, determine if the described route is valid or invalid.

All formulas should be represented in LaTeX. For example, the grid has dimensions \(M \times N\) and the moves are given as a string in \(\{U, D, L, R\}\).

inputFormat

The input is given from stdin and has the following format:

T
M N
K
x y movements
x y movements
... (K routes)
... (repeat for next test cases)

Where:

• T: the number of test cases.
• For each test case, the first line contains two integers \(M\) and \(N\) (the number of rows and columns of the grid).
• The next line contains an integer \(K\) representing the number of routes.
• Each of the next \(K\) lines contains a starting coordinate (\(x\), \(y\)) and a string representing the moves. The coordinates are 1-indexed.

All input is provided via standard input (stdin).

outputFormat

For each route in each test case, output a line containing either Valid or Invalid (without quotes) to stdout. The responses must appear in the same order as the routes in the input.

## sample

3
5 5
2
3 3 UURRDDL
2 2 RRUULL
4 4
1
1 1 RRD
3 3
1
2 2 RLL

Valid
Invalid
Valid
Invalid

</p>