5562. 2D Pinball (Hard)

请注意：本题存在对应的简单版本，两版本仅数据范围不同。保证通过了困难版本的提交可以通过简单版本。在当前版本中， $1 \le T \le 2 \times 10^5$ 。

$\texttt{SpadeZ}$ 有一个长方形的弹球桌，其上方为一个 $n$ 行 $m$ 列的网格，其中每一格均为正方形，每一格上面都可以放置障碍物。

我们使用包含两个字母的字符串表示弹珠的运动方向，左上为 LU ，左下为 LD ，右上为 RU ，右下为 RD 。弹珠的运动方向只会是这四种中的其中一种。

弹珠与弹球桌之间的摩擦力忽略不计，弹珠将从其中一格的中心位置开始，以每秒 $\sqrt{2}$ 格的速率匀速运动。当弹珠运动时如果运动方向的前方、左前方、右前方这三格均没有障碍物，弹珠将保持运动方向继续运动，否则弹珠将在 $0.5$ 秒后碰撞到障碍物，并根据障碍物的位置向不同的方向反弹（如下图）。由于弹珠的半径远小于弹球桌一格的边长，弹珠的半径对弹珠运动的微小影响忽略不计，也就是说我们认为在整数秒时弹珠一定位于某一格的中心位置。

$\texttt{SpadeZ}$ 在布置好弹球桌后， $\texttt{sha7dow}$ 带着他的同学们去找他玩弹球桌了！每一位同学都会发射一颗弹珠，只有上一位同学的弹珠运动完并被收回后，下一位同学才能发射下一颗弹珠。每一位同学会在他游玩的第 $0$ 秒发射一颗弹珠，而他们发现等待弹珠运动的过程非常漫长，排在后面的同学等不及想知道自己的弹珠在 $t$ 秒后会运动到哪一个位置了！给定弹球桌的布局、每一位同学的弹珠 $i$ 的初始位置和运动方向，请你计算出每一位同学的弹珠在第 $t_i$ 秒时的位置和运动方向。