Roboti

문제

Kile, a board games enthusiast, recently discovered the game Robots. The game consists of a board with $nn$ rows and $mm$ columns and one robot. The field $(1,1)(1,\; 1)$ is the top-left field of the board, while the field $(n,m)(n,\; m)$ is the bottom-right.

At the beginning, the robot is positioned on some field $(x,y)(x,\; y)$ ($xx$-th row, $yy$-th column), and the player can direct it in one of the four directions: up, down, left, or right. Depending on the chosen direction, it will move in that direction until it encounters its goal or a special field on the board. If at any point it wants to exit the board, it wraps around to the other side. For example, if it is located at the field $(n,3)(n,\; 3)$ and wants to move down, it will arrive at the field $(1,3)(1,\; 3)$.

The board has three types of fields:

• Empty field - the robot continues moving in the same direction
• Left turn field - when the robot steps on this field, it will turn left by $9090$° and continue moving
• Right turn field - when the robot steps on this field, it will turn right by $9090$° and continue moving

Most fields on the board are empty, only $kk$ of them are left or right turn fields.

The game consists of $qq$ rounds. In the $ii$-th round of the game, the robot will be placed on the field $(a_i,b_i)(a\_i\; ,\; b\_i)$. The goal is to reach the field $(c_i,d_i)(c\_i\; ,\; d\_i)$ using the minimum number of turns, or determine that it is impossible.

After playing this game several times, Kile realized that it is more challenging than it initially seemed. That is why he needs your help now. Help him determine the minimum number of turns required for each round of the game!

Note: If the robot starts or finishes its path on a left or right turn field, that turn is not counted.

입력

The first line contains integers $nn$, $mm$ and $kk$ (1 ≤ n, m ≤ 10^6, 0 ≤ k ≤ 10^5), the number of rows, columns and non-empty fields on the board.

The i-th of the following $nn$ lines contains integers $x_{i}x\_i$, $y_{i}y\_i$ and character $s_{i}s\_i$ (1 ≤ x_i ≤ n, 1 ≤ y_i ≤ m, $s_i=s\_i\; =$ ‘L’ or $s_i=s\_i\; =$ ‘R’), the row and column of $ii$-th turn field and the type of turn. If $s_i=s\_i\; =$ ‘L’ then it is a left turn field. If $s_i=s\_i\; =$ ‘R’ then it is a right turn field.

The next line contains integer $qq$ (1 ≤ q ≤ 3 \cdot 10^5), the number of rounds.

The $ii$-th of the following $qq$ lines contains integers $a_{i}a\_i$, $b_{i}b\_i$, $c_{i}c\_i$, $d_{i}d\_i$ (1 ≤ a_i , c_i ≤ n, 1 ≤ b_i , d_i ≤ m), the starting position and the goal.

출력

In the $ii$-th of the following $qq$ lines output the minimal number of turns for the $ii$-th round of the game or '-1' if it is impossible to reach the goal.

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