CF1607E.Robot on the Board 1

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.

The sequence of commands $s$ executed by the robot is given. Each command is denoted by one of the symbols 'L', 'R', 'D' or 'U', and triggers the movement to left, right, down or up, respectively.

The robot can start its movement in any cell. The robot executes the commands starting from the first one, strictly in the order in which they are listed in $s$. If the robot moves beyond the edge of the board, it falls and breaks. A command that causes the robot to break is not considered successfully executed.

The robot's task is to execute as many commands as possible without falling off the board. For example, on board $3 \times 3$, if the robot starts a sequence of actions $s=$"RRDLUU" ("right", "right", "down", "left", "up", "up") from the central cell, the robot will perform one command, then the next command will force him to cross the edge. If the robot starts moving from the cell $(2, 1)$ (second row, first column) then all commands will be executed successfully and the robot will stop at the cell $(1, 2)$ (first row, second column).

The robot starts from cell $(2, 1)$ (second row, first column). It moves right, right, down, left, up, and up. In this case it ends in the cell $(1, 2)$ (first row, second column).

Determine the cell from which the robot should start its movement in order to execute as many commands as possible.

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

机器人可以从当前格子移动到其四个相邻（上下左右）格子之一。

给定机器人执行的命令序列 $s$。每个命令用字符 'L'、'R'、'D' 或 'U' 中的一个表示，分别表示向左、向右、向下、向上移动。

机器人可在任意格子开始移动。机器人从第一个命令开始，严格按照 $s$ 中所列顺序依次执行命令。若机器人移出棋盘边界，则会坠落并损坏。导致机器人坠落的命令不被视为成功执行。

机器人的任务是执行尽可能多的命令而不坠出棋盘。例如，在 $3 \times 3$ 的棋盘上，若机器人从中心格子开始执行命令序列 $s =$ "RRDLUU"（即“右”、“右”、“下”、“左”、“上”、“上”），则仅能成功执行一条命令，随后的命令将使其越出边界；而若机器人从格子 $(2, 1)$（第 $2$ 行、第 $1$ 列）开始移动，则所有命令均可成功执行，最终停在格子 $(1, 2)$（第 $1$ 行、第 $2$ 列）。

机器人从格子 $(2, 1)$（第 $2$ 行、第 $1$ 列）出发，依次向右、向右、向下、向左、向上、向上移动。最终停在格子 $(1, 2)$（第 $1$ 行、第 $2$ 列）。

请确定机器人应从哪个格子出发，才能执行最多数量的命令。

The first line contains an integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases.

The next $2t$ lines contain descriptions of the test cases.

In the description of each test case, the first line contains two integers $n$ and $m$ ($1 \leq n, m \leq 10^6$) — the height and width of the field that the robot is located on. The second line of the description is a string $s$ consisting solely of characters 'L', 'R', 'D' and 'U' — the sequence of commands the robot executes. The string has a length from $1$ to $10^6$ commands.

It is guaranteed that the total length of $s$ over all test cases does not exceed $10^6$.

第一行包含一个整数 $t$（$1 \leq t \leq 10^4$）—— 测试用例的数量。

接下来的 $2t$ 行包含各测试用例的描述。

在每个测试用例的描述中，第一行包含两个整数 $n$ 和 $m$（$1 \leq n, m \leq 10^6$）—— 机器人所在场地的高度和宽度。描述的第二行是一个字符串 $s$，仅由字符 'L'、'R'、'D' 和 'U' 组成——表示机器人执行的指令序列。该字符串长度为 $1$ 至 $10^6$。

保证所有测试用例中字符串 $s$ 的总长度不超过 $10^6$。

Print $t$ lines, each of which contains the answer to the corresponding test case. The answer to the test case are two integers $r$ ($1 \leq r \leq n$) and $c$ ($1 \leq c \leq m$), separated by a space — the coordinates of the cell (row number and column number) from which the robot should start moving to perform as many commands as possible.

If there are several such cells, you may output any of them.

输出 $t$ 行，每行包含对应测试用例的答案。每个测试用例的答案为两个整数 $r$（$1 \leq r \leq n$）和 $c$（$1 \leq c \leq m$），以空格分隔——表示机器人应从该单元格（行号和列号）出发移动，以执行尽可能多的指令。

若存在多个满足条件的单元格，可输出其中任意一个。