题目背景

译自 COCI 2023/2024 Contest #4 T5「Roboti」

题目描述

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 2 2
1 1 L
2 2 R
5
1 1 2 2
2 1 1 2
1 1 1 2
2 1 1 1
2 2 2 1

-1
1
0
0
0

3 3 4
1 1 L
1 3 L
2 1 L
3 3 L
7
1 1 3 3
3 3 2 1
3 1 2 2
2 3 1 2
2 3 3 1
1 2 3 2
3 3 2 2

1
2
1
1
1
0
3

4 4 8
1 1 R
1 3 L
2 2 R
2 4 L
3 1 L
3 3 L
4 2 L
4 4 L
7
1 2 1 4
2 2 3 4
4 4 3 2
4 1 4 4
4 2 3 1
1 2 2 3
2 4 2 3

2
1
1
0
-1
5
0

提示

样例解释 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$