{"raw_statement":[{"iden":"background","content":"**译自 [COCI 2023/2024 Contest #4](https://hsin.hr/coci/archive/2023_2024) T5「[Roboti](https://hsin.hr/coci/archive/2023_2024/contest4_tasks.pdf)」**"},{"iden":"statement","content":"Kile 是一个桌游爱好者，他最近发现了一个叫做 Robots 的游戏。这个游戏由一个 $n$ 行 $m$ 列的网格和一个机器人组成。位置 $(1, 1)$ 是棋盘的左上角，位置 $(n, m)$ 是右下角。\n\n开始时，机器人位于某个位置 $(x, y)$（第 $x$ 行，第 $y$ 列），玩家可以将其朝上下左右之一的方向进行移动。根据选择的方向，它将沿着该方向移动，直到到达目标格或网格中的特殊格。如果在任何时候机器人想要离开棋盘，它将翻折到另一侧。例如，如果它位于位置 $(n, 3)$ 并希望向下移动，它将到达位置 $(1, 3)$。\n\n棋盘上有三种类型的位置：\n\n- 空格：机器人朝相同的方向继续移动；\n- 左转格：当机器人进入此格时，它会左转 $90$ 度并继续移动；\n- 右转格：当机器人进入此格时，它会右转 $90$ 度并继续移动。\n\n网格中大部分位置都是空格，只有 $k$ 个位置是左转或右转格。\n\n游戏由 $q$ 轮组成。在第 $i$ 轮中，机器人将被放置在位置 $(a_i, b_i)$。目标是使用最少的转弯次数到达位置 $(c_i, d_i)$，或判定这是不可能的。\n\n在多次玩这个游戏后，Kile 意识到它比起初看起来要更具挑战性。这就是为什么他现在需要你的帮助。帮助他确定每一轮游戏所需的最小转弯次数！\n\n**注意**：如果机器人路径的起点或终点位于左转或右转格上，则该格不起作用。"},{"iden":"input","content":"第一行包含三个整数 $n,m,k\\ (1\\le n,m\\le 10^6,0\\le k\\le 10^5)$，分别表示行数，列数和网格中非空格的个数。\n\n接下来 $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`，则表示这是一个右转格。\n\n接下来一行一个整数 $q\\ (1\\le q\\le 3\\cdot 10^5)$，表示游戏轮数。\n\n接下来 $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)$，分别表示起始和目标位置。"},{"iden":"output","content":"输出 $q$ 行，第 $i$ 行输出第 $i$ 轮所需的最小转弯次数，如果无法到达目标，则输出 $-1$。"},{"iden":"note","content":"### 样例解释 2\n\n第一轮：从 $(1, 1)$ 开始。如果初始机器人向左移动，它将在下一步到达 $(1, 3)$，因为它想要离开棋盘，所以会从另一侧进入。位置 $(1, 3)$ 是一个左转格，所以机器人将朝下方向移动。再经过两步，它将到达目标位置 $(3, 3)$​。\n\n第二轮：从 $(3, 3)$ 开始。如果初始机器人向上移动，它将在两步后到达 $(1, 3)$，在那里由于左转格而向左转。再经过两步，它将到达位置 $(1, 1)$，这也是一个左转格，所以它将向下移动。在下一步中，它将到达目标位置 $(2, 1)$。\n\n### 子任务\n\n| 子任务编号 |       附加限制       | 分值 |\n| :--------: | :------------------: | :--: |\n|    $1$     |        $k=0$         | $10$  |\n|    $2$     | $n,m\\le 300,q\\le 10$ | $13$ |\n|    $3$     |     $n,m\\le 300$     | $49$ |\n|    $4$     |      无附加限制      | $38$ |"}],"translated_statement":null,"sample_group":[["2 2 2\n1 1 L\n2 2 R\n5\n1 1 2 2\n2 1 1 2\n1 1 1 2\n2 1 1 1\n2 2 2 1\n","-1\n1\n0\n0\n0\n"],["3 3 4\n1 1 L\n1 3 L\n2 1 L\n3 3 L\n7\n1 1 3 3\n3 3 2 1\n3 1 2 2\n2 3 1 2\n2 3 3 1\n1 2 3 2\n3 3 2 2\n","1\n2\n1\n1\n1\n0\n3\n"],["4 4 8\n1 1 R\n1 3 L\n2 2 R\n2 4 L\n3 1 L\n3 3 L\n4 2 L\n4 4 L\n7\n1 2 1 4\n2 2 3 4\n4 4 3 2\n4 1 4 4\n4 2 3 1\n1 2 2 3\n2 4 2 3\n","2\n1\n1\n0\n-1\n5\n0\n"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}