310269: CF1807F. Bouncy Ball

F. Bouncy Balltime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

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.

Input

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$.

Output

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.

ExampleInput

6
5 7 1 7 2 4 DL
5 7 1 7 3 2 DL
3 3 1 3 2 2 UR
2 4 2 1 2 2 DR
4 3 1 1 1 3 UL
6 4 1 2 3 4 DR

Output

3
-1
1
-1
4
0

题目大意：
你有一个可以表示为 $ 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) $。

每一步之后，除非球撞到墙（即方向会使球在下一步超出房间的边界），球将保持其方向。在这种情况下，球的方向会在墙的轴上翻转；如果球撞到角落，两个方向都会翻转。任何此类情况都称为反弹。球永远不会停止移动。

任务是找出球到达 $ (i_2, j_2) $ 单元格之前会经历多少次反弹，或者如果球永远不会到达 $ (i_2, j_2) $ 单元格，则打印 $ -1 $。

输入输出数据格式：
输入：
- 第一行包含一个整数 $ 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 $。

输出：
- 对于每个测试用例，输出一个整数——球到达 $ (i_2, j_2) $ 单元格之前经历的反弹次数，或者如果球永远不会到达最终单元格，则输出 $ -1 $。题目大意： 你有一个可以表示为 $ 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) $。 每一步之后，除非球撞到墙（即方向会使球在下一步超出房间的边界），球将保持其方向。在这种情况下，球的方向会在墙的轴上翻转；如果球撞到角落，两个方向都会翻转。任何此类情况都称为反弹。球永远不会停止移动。 任务是找出球到达 $ (i_2, j_2) $ 单元格之前会经历多少次反弹，或者如果球永远不会到达 $ (i_2, j_2) $ 单元格，则打印 $ -1 $。 输入输出数据格式： 输入： - 第一行包含一个整数 $ 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 $。 输出： - 对于每个测试用例，输出一个整数——球到达 $ (i_2, j_2) $ 单元格之前经历的反弹次数，或者如果球永远不会到达最终单元格，则输出 $ -1 $。