B. Paths in the Sand
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

To celebrate how well they did in the contest, Jacobo has taken the finalists of the OIE to the beach. They have decided to build a huge maze so that when a wave breaks, the water will reach the entrance and follow the path to the goal. Since they don't have much time, they will divide the work, and each one will build a part of the path.

Specifically, they have divided the work into a grid of size $$$n \times n$$$, with $$$n^2$$$ cells, which we can refer to by their coordinates $$$(f, c)$$$, where $$$1 \leq f \leq n$$$ is the row and $$$1 \leq c \leq n$$$ is the column. The water will start from cell $$$(1, 1)$$$ and will reach cell $$$(n, 1)$$$ after passing exactly once through each of the $$$n^2$$$ cells of the grid. Marco has given them a map where, in each cell, he has written a letter from the set $$$\{L, R, U, D\}$$$ to indicate which direction the water should follow upon entering the cell (these letters translate to left, right, up, and down by their initials in English). For example, if a cell $$$(f, c)$$$ contains the letter $$$U$$$, the water will move to cell $$$(f-1, c)$$$, since $$$U$$$ indicates that it moves upwards. Cell $$$(n, 1)$$$ contains an $$$X$$$, as that is where the path ends, and there will simply be a deep hole to collect the water.

However, Marco has set a trap for them: one of the cells has the wrong letter. Can you find out which cell it is and what letter it should have in order for the map to meet the requirements?

Input

The first line contains an integer $$$T$$$: the number of cases. For each case, the first line contains an integer $$$n$$$, the length (and width) of the grid. This is followed by $$$n$$$ lines, each with $$$n$$$ characters representing the letters of the corresponding row of the grid.

Output

For each case, print a line with two integers separated by a space: $$$f$$$ and $$$c$$$, the row and column of the wrong cell, followed by the letter that should have been in its place.

Scoring
  1. (17 points) $$$n = 2$$$.
  2. (39 points) $$$n \leq 50$$$ and the sum of $$$n^4$$$ for all cases is less than or equal to $$$50^4$$$.
  3. (44 points) No additional restrictions.
Example
Input
2
2
LD
XL
3
DRD
RUL
XLL
Output
1 1 R
2 3 D
Note
  • $$$1 \leq T \leq 2000$$$.
  • $$$2 \leq n \leq 10^3$$$.
  • The sum of $$$n^2$$$ for all cases is less than or equal to $$$10^6$$$.