给你一个可以用 $$$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)$$$。
每一步之后,球都会保持其方向,除非它撞到墙壁(即,该方向在下一步中将其带出房间的边界)。在这种情况下,球的方向沿着墙的轴线翻转;如果球撞到角落,两个方向都会翻转。任何这种情况都称为反弹。球永远不会停止移动。
在上面的示例中,球从 $$$(1, 7)$$$ 开始,经过 $$$\texttt{DL}$$$ 直到到达底壁,然后弹起并继续朝 $$$\texttt{UL}$$$ 方向移动。到达左侧墙壁后,球弹起并继续朝 $$$\texttt{UR}$$$ 方向移动。当球到达上墙时,它会弹起并继续沿 $$$\texttt{DR}$$$ 方向移动。到达右下角后,它会弹起一次,并继续朝 $$$\texttt{UL}$$$ 方向前进,依此类推。
你的任务是找出球在到达房间中的单元格 $$$(i_2, j_2)$$$ 之前会经历多少次弹跳,或者通过打印 $$$-1$$$ 来报告它从未到达单元格 $$$(i_2, j_2)$$$。
请注意,球首先进入单元格,只有在需要时才会反弹。
输入
第一行包含一个整数 $$$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$$$。
示例
输入 #1
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
输出 #1
3 -1 1 -1 4 0