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 × 105) (2 ≤ k ≤ 109), 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 sr, sc, the row and the column of the starting cell (a free cell). Followed by a single uppercase letter sdir, 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:
Note that the robot performs the given instructions in the given order.
The total number of cells in all test cases doesn't exceed 106.
The total number of instructions in all test cases doesn't exceed 2 × 106.
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.
## Input
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 × 105) (2 ≤ k ≤ 109), 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 sr, sc, the row and the column of the starting cell (a free cell). Followed by a single uppercase letter sdir, 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 ≤ 107). Note that the robot performs the given instructions in the given order.The total number of cells in all test cases doesn't exceed 106.The total number of instructions in all test cases doesn't exceed 2 × 106.
## Output
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.
[samples]
**Definitions**
Let $ T \in \mathbb{Z} $ be the number of test cases.
For each test case:
- Let $ r, c \in \mathbb{Z} $ be the grid dimensions ($ 3 \leq r, c \leq 500 $).
- Let $ q \in \mathbb{Z} $ be the number of instructions ($ 1 \leq q \leq 2 \times 10^5 $).
- Let $ k \in \mathbb{Z} $ be the number of colors per cell ($ 2 \leq k \leq 10^9 $).
- Let $ (s_r, s_c) \in \{1, \dots, r\} \times \{1, \dots, c\} $ be the starting position (free cell).
- Let $ d_0 \in \{\text{U}, \text{D}, \text{L}, \text{R}\} $ be the initial direction.
- Let $ G \in \{\text{.}, \#\}^{r \times c} $ be the grid, where $ G[i][j] = \text{.} $ iff cell $ (i,j) $ is free.
- Let $ I = (i_1, i_2, \dots, i_q) $ be the sequence of instructions, each $ i_j \in \{\text{F}, \text{L}, \text{R}\} $:
- F: move forward one cell in current direction (if possible),
- L: rotate left 90°,
- R: rotate right 90°.
- Let $ C: \{(i,j) \mid G[i][j] = \text{.}\} \to \mathbb{N} $ be the color counter per free cell, initialized to $ C(i,j) = 0 $, incremented each time the robot visits $ (i,j) $.
**Constraints**
1. $ 1 \leq T \leq 64 $
2. Grid borders are all blocked; each free cell has at least one adjacent free cell.
3. Total grid cells across test cases $ \leq 10^6 $.
4. Total instructions across test cases $ \leq 2 \times 10^6 $.
5. Robot explodes when $ C(i,j) = k $ upon visiting cell $ (i,j) $.
6. Rotation takes 0 time; each move (F) takes 1 time unit.
**Objective**
Simulate the robot’s path step-by-step:
- At time $ t = 0 $, robot is at $ (s_r, s_c) $ with direction $ d_0 $.
- For each instruction $ i_j $ ($ j = 1 $ to $ q $):
- If $ i_j \in \{\text{L}, \text{R}\} $: update direction (no time cost).
- If $ i_j = \text{F} $:
- Compute next cell $ (n_r, n_c) $ in current direction.
- If $ (n_r, n_c) $ is blocked or out of bounds: stay, no color change.
- Else:
- Increment $ C(n_r, n_c) \gets C(n_r, n_c) + 1 $.
- If $ C(n_r, n_c) = k $: **explode** at $ (n_r, n_c) $ at time $ t = j $.
- Else: move to $ (n_r, n_c) $, update position.
- If no explosion occurs after all instructions: output $-1$.
- Output: if exploded, print $ (n_r, n_c, t) $; else print $-1$.