Kile 是一位棋盘游戏爱好者，最近发现了“机器人”游戏。游戏在一个有 $n$ 行 $m$ 列的棋盘上进行，棋盘上有一个机器人。$(1, 1)$ 是棋盘的左上角，$(n, m)$ 是右下角。

游戏开始时，机器人位于某个格子 $(x, y)$（第 $x$ 行，第 $y$ 列），玩家可以指挥它向四个方向之一移动：上、下、左或右。根据所选方向，它将沿该方向移动，直到遇到目标或棋盘上的特殊格子。如果它在任何时候想要离开棋盘，它会从另一侧绕回。例如，如果它位于格子 $(n, 3)$ 并想要向下移动，它将到达格子 $(1, 3)$。

棋盘上有三种类型的格子： 空地 - 机器人保持原方向继续移动 左转格子 - 当机器人踏上此格子时，它将向左转 $90^\circ$ 并继续移动 * 右转格子 - 当机器人踏上此格子时，它将向右转 $90^\circ$ 并继续移动

棋盘上的大多数格子都是空的，只有 $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$)，分别表示棋盘的行数、列数和非空格子数。

接下来的 $n$ 行中，第 $i$ 行包含整数 $x_i, y_i$ 和字符 $s_i$ ($1 \le x_i \le n, 1 \le y_i \le m, s_i = \text{'L'}$ 或 $s_i = \text{'R'}$)，表示第 $i$ 个转弯格子的行、列及其转弯类型。如果 $s_i = \text{'L'}$，则它是左转格子。如果 $s_i = \text{'R'}$，则它是右转格子。

下一行包含整数 $q$ ($1 \le q \le 3 \cdot 10^5$)，表示轮数。

接下来的 $q$ 行中，第 $i$ 行包含整数 $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'。

子任务

样例

样例输入 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
1
0
0
0

样例输入 2

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

样例输出 2

1
2
1
1
1
0
3

样例输入 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

样例输出 3

2
1
1
0
-1
5
0

说明

第二个样例的说明： 第一轮：我们从 $(1, 1)$ 开始。如果我们指挥机器人向左移动，它将在下一步到达 $(1, 3)$，因为它想要离开棋盘，所以它会从另一侧绕回。格子 $(1, 3)$ 是一个左转格子，所以机器人现在向下移动。再走两步后，它将到达目标 $(3, 3)$。

第二轮：我们从 $(3, 3)$ 开始。如果我们指挥机器人向上移动，它将在两步后到达 $(1, 3)$，在那里它会因为左转格子而向左转。两步后，它将到达格子 $(1, 1)$，这也是一个左转格子，所以它会向下转。下一步，它将到达目标 $(2, 1)$。

Figure 1. 机器人游戏棋盘示意图