404682: GYM101608 F Robot II - Colorful Grid

Note that the description of the grid, and the movement instructions are the same as in problem Robot I - Instruction Reduction.

Instead of rewriting the instructions to fit on the SD card, you decided to buy a new one with larger capacity. Now, you are facing a new problem. Each free cell can be lit by one of k different colors. Initially, all the free cells are lit with the first color (white). Each time the robot visits a cell, it changes its color to a new color that wasn’t used in that cell before. If all color were used, the robot explodes.

Given the initial position and direction of the robot, the grid, and the movement instructions, determine the position of the cell that the robot will explode at and the total amount of time the robot took from the start until it exploded. Note that rotation takes no time.

The first line of input contains a single integer T (1 ≤ T ≤ 64), the number of test cases.

The first line of each test case contains four integers r, c, q, and k (3 ≤ r, c ≤ 500) (1 ≤ q ≤ 2 × 10⁵) (2 ≤ k ≤ 10⁹), the number of rows and columns of the grid, the number of instructions in the file, and the number of different colors for each cell, respectively.

The second line of each test case contains two integers s_r, s_c, the row and the column of the starting cell (a free cell). Followed by a single uppercase letter s_dir, which is the initial direction of the robot, it can be only one of the four letters {'U', 'D', 'L', 'R'}, each letter represents one of the four directions: up, down, left, and right, respectively.

Each of the following r lines contains c characters that are either ‘.’ (a free cell), or ‘#’ (a blocked cell). It is guaranteed that each free cell has at least one adjacent free cell, and all cells on the border of the grid are blocked.

Each of the following q lines contains an instruction, each instruction will be in one of two formats:

• ‘R’ , that represents the first type of movement “Rotate”.
• ‘F’ x, that represents the second type of movement “Move x” (1 ≤ x ≤ 10⁷).

Note that the robot performs the given instructions in the given order.

The total number of cells in all test cases doesn't exceed 10⁶.

The total number of instructions in all test cases doesn't exceed 2 × 10⁶.

For each test case, print three integers, the row and column of the cell that the robot will explode at, and elapsed time until then. If it will not explode print only  - 1.

2
5 7 3 2
3 3 R
#######
#.....#
#...#.#
#.....#
#######
F 5
R
F 3
3 6 1 2
2 2 U
######
#....#
######
F 3

3 4 7
-1