CF1807F.Bouncy Ball

You are given a room that can be represented by a $n \times m$ grid. There is a ball at position $(i_1, j_1)$ (the intersection of row $i_1$ and column $j_1$), and it starts going diagonally in one of the four directions:

• The ball is going down and right, denoted by $\texttt{DR}$; it means that after a step, the ball's location goes from $(i, j)$ to $(i+1, j+1)$.
• The ball is going down and left, denoted by $\texttt{DL}$; it means that after a step, the ball's location goes from $(i, j)$ to $(i+1, j-1)$.
• The ball is going up and right, denoted by $\texttt{UR}$; it means that after a step, the ball's location goes from $(i, j)$ to $(i-1, j+1)$.
• The ball is going up and left, denoted by $\texttt{UL}$; it means that after a step, the ball's location goes from $(i, j)$ to $(i-1, j-1)$.

After each step, the ball maintains its direction unless it hits a wall (that is, the direction takes it out of the room's bounds in the next step). In this case, the ball's direction gets flipped along the axis of the wall; if the ball hits a corner, both directions get flipped. Any instance of this is called a bounce. The ball never stops moving.

In the above example, the ball starts at $(1, 7)$ and goes $\texttt{DL}$ until it reaches the bottom wall, then it bounces and continues in the direction $\texttt{UL}$. After reaching the left wall, the ball bounces and continues to go in the direction $\texttt{UR}$. When the ball reaches the upper wall, it bounces and continues in the direction $\texttt{DR}$. After reaching the bottom-right corner, it bounces once and continues in direction $\texttt{UL}$, and so on.

Your task is to find how many bounces the ball will go through until it reaches cell $(i_2, j_2)$ in the room, or report that it never reaches cell $(i_2, j_2)$ by printing $-1$.

Note that the ball first goes in a cell and only after that bounces if it needs to.

你被给定一个可表示为 $n \times m$ 网格的房间。球初始位于位置 $(i_1, j_1)$（即第 $i_1$ 行与第 $j_1$ 列的交点），并以以下四种对角线方向之一开始运动：

• 球向右下运动，记为 $\texttt{DR}$；表示每一步后，球的位置从 $(i, j)$ 变为 $(i+1, j+1)$。
• 球向左下运动，记为 $\texttt{DL}$；表示每一步后，球的位置从 $(i, j)$ 变为 $(i+1, j-1)$。
• 球向右上运动，记为 $\texttt{UR}$；表示每一步后，球的位置从 $(i, j)$ 变为 $(i-1, j+1)$。
• 球向左上运动，记为 $\texttt{UL}$；表示每一步后，球的位置从 $(i, j)$ 变为 $(i-1, j-1)$。

每步之后，球保持当前运动方向，除非它将撞到墙壁（即下一步按当前方向移动会使其移出房间边界）。此时，球的运动方向将沿该墙壁所在轴线翻转；若球撞到角落，则两个方向均被翻转。此类情形统称为“反弹”（bounce）。球永不停止运动。

在上述示例中，球起始于 $(1, 7)$，沿 $\texttt{DL}$ 方向运动，直至抵达底墙，然后反弹并继续沿 $\texttt{UL}$ 方向运动。到达左墙后再次反弹，并继续沿 $\texttt{UR}$ 方向运动。当球抵达顶墙时，再次反弹并继续沿 $\texttt{DR}$ 方向运动。抵达右下角后，反弹一次并继续沿 $\texttt{UL}$ 方向运动，依此类推。

你的任务是：计算球在抵达房间内目标格子 $(i_2, j_2)$ 之前所经历的反弹次数；若球永远无法抵达 $(i_2, j_2)$，则输出 $-1$。

注意：球总是先移动进入某一格子，之后才在需要时发生反弹。

The first line contains a single integer $t$ ($1 \leq t \leq 1000$) — the number of test cases.

The first line of each test case contains six integers and a string $n, m, i_1, j_1, i_2, j_2, d$ ($2 \leq n, m \leq 25000$; $1 \leq i_1, i_2 \leq n$; $1 \leq j_1, j_2 \leq m$; $d \in{ \texttt{DR}, \texttt{DL}, \texttt{UR}, \texttt{UL}}$) — the dimensions of the grid, the starting coordinates of the ball, the coordinates of the final cell and the starting direction of the ball.

It is guaranteed that the sum of $n \cdot m$ over all test cases does not exceed $5 \cdot 10^4$.

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

每个测试用例的第一行包含六个整数和一个字符串 $n, m, i_1, j_1, i_2, j_2, d$（$2 \leq n, m \leq 25000$；$1 \leq i_1, i_2 \leq n$；$1 \leq j_1, j_2 \leq m$；$d \in \{ \texttt{DR}, \texttt{DL}, \texttt{UR}, \texttt{UL} \}$）—— 网格的尺寸、球的起始坐标、目标单元格的坐标以及球的初始运动方向。

保证所有测试用例中 $n \cdot m$ 的总和不超过 $5 \cdot 10^4$。

For each test case, output a single integer — the number of bounces the ball does until it reaches cell $(i_2, j_2)$ for the first time, or $-1$ if the ball never reaches the final cell.

对于每个测试用例，输出一个整数——球首次到达单元格 $(i_2, j_2)$ 所经历的弹跳次数；若球永远无法到达目标单元格，则输出 $-1$。