Problem Description

Kile is a board game enthusiast who recently discovered a game called Robots. The game consists of a grid of $n$ rows and $m$ columns and a robot. The position $(1, 1)$ is the top-left corner of the board, and the position $(n, m)$ is the bottom-right corner.

Initially, the robot is located at a position $(x, y)$ (the $x$-th row, the $y$-th column), and the player can move it in one of the four directions: up, down, left, or right. It will move in the chosen direction until it reaches a target cell or a special cell on the grid. If at any point the robot attempts to leave the board, it will wrap around to the other side. For example, if it is at position $(n, 3)$ and wants to move down, it will end up at position $(1, 3)$.

There are three types of positions on the board:

• Empty: The robot continues moving in the same direction.
• Left-turn: When the robot enters this cell, it turns $90$ degrees to the left and continues moving.
• Right-turn: When the robot enters this cell, it turns $90$ degrees to the right and continues moving.

Most positions on the grid are empty, with only $k$ positions being left-turn or right-turn cells.

The game consists of $q$ rounds. In the $i$-th round, the robot is placed at position $(a_i, b_i)$. The goal is to reach position $(c_i, d_i)$ with the minimum number of turns, or determine that it is impossible.

After playing this game multiple times, Kile realizes it is more challenging than it initially seems. This is why he now needs your help. Help him determine the minimum number of turns required for each round of the game!

Note: If the starting or ending position of the robot's path is a left-turn or right-turn cell, that cell does not affect the robot.

Input Format

The first line contains three integers $n, m, k$ $(1 \le n, m \le 10^6, 0 \le k \le 10^5)$, representing the number of rows, columns, and the number of non-empty cells on the grid, respectively.

The next $k$ lines each contain two integers $x_i, y_i$ $(1 \le x_i \le n, 1 \le y_i \le m)$ and a character $s_i$ $(s_i \in \{\texttt{L}, \texttt{R}\})$, representing the position and type of the $i$-th special cell. If $s_i$ is L, it is a left-turn cell. If $s_i$ is R, it is a right-turn cell.

The next line contains an integer $q$ $(1 \le q \le 3 \cdot 10^5)$, representing the number of game rounds.

The next $q$ lines each contain four integers $a_i, b_i, c_i, d_i$ $(1 \le a_i, c_i \le n, 1 \le b_i, d_i \le m)$, representing the starting and target positions for each round.

Output Format

Output $q$ lines, where the $i$-th line contains the minimum number of turns required for the $i$-th round, or $-1$ if it is impossible to reach the target.

Sample Input and Output

Sample Input #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

Sample Output #1

-1
1
0
0
0

Sample Input #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

Sample Output #2

1
2
1
1
1
0
3

Sample Input #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

Sample Output #3

2
1
1
0
-1
5
0

Notes/Hints

Sample Explanation 2

First round: Starting from $(1, 1)$. If the initial direction is left, it will reach $(1, 3)$ on the next step, as it wraps around the board. The position $(1, 3)$ is a left-turn cell, so the robot will move downwards. After two more steps, it will reach the target position $(3, 3)$.

Second round: Starting from $(3, 3)$. If the initial direction is up, it will reach $(1, 3)$ after two steps, where it will turn left due to the left-turn cell. After two more steps, it will reach position $(1, 1)$, which is also a left-turn cell, so it will move downwards. In the next step, it will reach the target position $(2, 1)$.

Subtasks

见题面 Input 部分

见题面 Output 部分