CF1607F.Robot on the Board 2

The robot is located on a checkered rectangular board of size $n \times m$ ($n$ rows, $m$ columns). The rows in the board are numbered from $1$ to $n$ from top to bottom, and the columns — from $1$ to $m$ from left to right.

The robot is able to move from the current cell to one of the four cells adjacent by side.

Each cell has one of the symbols 'L', 'R', 'D' or 'U' written on it, indicating the direction in which the robot will move when it gets in that cell — left, right, down or up, respectively.

The robot can start its movement in any cell. He then moves to the adjacent square in the direction indicated on the current square in one move.

• If the robot moves beyond the edge of the board, it falls and breaks.
• If the robot appears in the cell it already visited before, it breaks (it stops and doesn't move anymore).

Robot can choose any cell as the starting cell. Its goal is to make the maximum number of steps before it breaks or stops.

Determine from which square the robot should start its movement in order to execute as many commands as possible. A command is considered successfully completed if the robot has moved from the square on which that command was written (it does not matter whether to another square or beyond the edge of the board).

机器人位于一个 $n \times m$（$n$ 行，$m$ 列）的方格矩形棋盘上。棋盘的行从上到下编号为 $1$ 至 $n$，列从左到右编号为 $1$ 至 $m$。

机器人可以从当前格子移动到四个与之边相邻的格子之一。

每个格子上标有一个字符：'L'、'R'、'D' 或 'U'，分别表示当机器人进入该格子时将要移动的方向：左、右、下、上。

机器人可任选一个格子作为起始位置，然后在每一步中，根据当前所在格子上所标注的方向，向相邻格子移动一格。

• 若机器人移出棋盘边界，则会坠落并损坏；
• 若机器人进入一个它之前已访问过的格子，则会损坏（即停止运行，不再移动）。

机器人可任选一个格子作为起始格子。其目标是在损坏或停止前，尽可能多地执行移动步数。

请确定机器人应从哪个格子出发，才能执行最多的指令。若机器人从某格子（该格子上写有某条指令）出发并执行了该指令（即从该格子移出，无论移向另一格子还是移出棋盘边界），则该指令即视为成功执行。

The first line contains an integer $t$ ($1 \le t \le 10000$) — the number of test cases in the test.

Each test case's description is preceded by a blank line. Next is a line that contains integers $n$ and $m$ ($1 \le n \le 2000$; $1 \le m \le 2000$) — the height and width of the board. This line followed by $n$ lines, the $i$-th of which describes the $i$-th line of the board. Each of them is exactly $m$ letters long and consists of symbols 'L', 'R', 'D' and 'U'.

It is guaranteed that the sum of sizes of all boards in the input does not exceed $4\cdot10^6$.

第一行包含一个整数 $t$（$1 \le t \le 10000$）—— 表示测试用例的数量。

每个测试用例的描述前均有一空行。接下来是一行，包含两个整数 $n$ 和 $m$（$1 \le n \le 2000$；$1 \le m \le 2000$）—— 分别表示棋盘的高度与宽度。随后是 $n$ 行，其中第 $i$ 行描述棋盘的第 $i$ 行。每行恰好由 $m$ 个字符组成，且仅包含字符 'L'、'R'、'D' 和 'U'。

保证输入中所有棋盘的尺寸总和不超过 $4\cdot10^6$。

For each test case, output three integers $r$, $c$ and $d$ ($1 \le r \le n$; $1 \le c \le m$; $d \ge 0$), which denote that the robot should start moving from cell $(r, c)$ to make the maximum number of moves $d$. If there are several answers, output any of them.

对于每个测试用例，输出三个整数 $r$、$c$ 和 $d$（$1 \le r \le n$；$1 \le c \le m$；$d \ge 0$），表示机器人应从单元格 $(r, c)$ 出发，以实现最大移动步数 $d$。若存在多个答案，输出任意一个即可。