P10232 [COCI 2023/2024 #4] Roboti

**译自 [COCI 2023/2024 Contest #4](https://hsin.hr/coci/archive/2023_2024) T5「[Roboti](https://hsin.hr/coci/archive/2023_2024/contest4_tasks.pdf)」**

Kile 是一个桌游爱好者，他最近发现了一个叫做 Robots 的游戏。这个游戏由一个 $n$ 行 $m$ 列的网格和一个机器人组成。位置 $(1, 1)$ 是棋盘的左上角，位置 $(n, m)$ 是右下角。 开始时，机器人位于某个位置 $(x, y)$（第 $x$ 行，第 $y$ 列），玩家可以将其朝上下左右之一的方向进行移动。根据选择的方向，它将沿着该方向移动，直到到达目标格或网格中的特殊格。如果在任何时候机器人想要离开棋盘，它将翻折到另一侧。例如，如果它位于位置 $(n, 3)$ 并希望向下移动，它将到达位置 $(1, 3)$。 棋盘上有三种类型的位置： - 空格：机器人朝相同的方向继续移动； - 左转格：当机器人进入此格时，它会左转 $90$ 度并继续移动； - 右转格：当机器人进入此格时，它会右转 $90$ 度并继续移动。 网格中大部分位置都是空格，只有 $k$ 个位置是左转或右转格。 游戏由 $q$ 轮组成。在第 $i$ 轮中，机器人将被放置在位置 $(a_i, b_i)$。目标是使用最少的转弯次数到达位置 $(c_i, d_i)$，或判定这是不可能的。 在多次玩这个游戏后，Kile 意识到它比起初看起来要更具挑战性。这就是为什么他现在需要你的帮助。帮助他确定每一轮游戏所需的最小转弯次数！ **注意**：如果机器人路径的起点或终点位于左转或右转格上，则该格不起作用。

第一行包含三个整数 $n,m,k\ (1\le n,m\le 10^6,0\le k\le 10^5)$，分别表示行数，列数和网格中非空格的个数。 接下来 $k$ 行，每行两个整数 $x_i,y_i\ (1\le x_i\le n,1\le y_i\le m)$ 和一个字符 $s_i\ (s_i\in \{\texttt{L},\texttt{R}\})$，分别表示第 $i$ 个特殊格的位置和类别。如果 $s_i$ 是 `L`，则表示这是一个左转格。如果是 `R`，则表示这是一个右转格。 接下来一行一个整数 $q\ (1\le q\le 3\cdot 10^5)$，表示游戏轮数。 接下来 $q$ 行，每行四个整数 $a_i,b_i,c_i,d_i\ (1\le a_i,c_i\le n,1\le b_i,d_i\le m)$，分别表示起始和目标位置。

输出 $q$ 行，第 $i$ 行输出第 $i$ 轮所需的最小转弯次数，如果无法到达目标，则输出 $-1$。

### 样例解释 2 第一轮：从 $(1, 1)$ 开始。如果初始机器人向左移动，它将在下一步到达 $(1, 3)$，因为它想要离开棋盘，所以会从另一侧进入。位置 $(1, 3)$ 是一个左转格，所以机器人将朝下方向移动。再经过两步，它将到达目标位置 $(3, 3)$​。 第二轮：从 $(3, 3)$ 开始。如果初始机器人向上移动，它将在两步后到达 $(1, 3)$，在那里由于左转格而向左转。再经过两步，它将到达位置 $(1, 1)$，这也是一个左转格，所以它将向下移动。在下一步中，它将到达目标位置 $(2, 1)$。 ### 子任务 | 子任务编号 | 附加限制 | 分值 | | :--------: | :------------------: | :--: | | $1$ | $k=0$ | $10$ | | $2$ | $n,m\le 300,q\le 10$ | $13$ | | $3$ | $n,m\le 300$ | $49$ | | $4$ | 无附加限制 | $38$ |