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

At the beginning, the robot is positioned on some field ~(x, y)~ (~x~-th row, ~y~-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)~ and wants to move down, it will arrive at the field ~(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 ~90^\circ~ and continue moving.
• Right turn field — when the robot steps on this field, it will turn right by ~90^\circ~ and continue moving.

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

The game consists of ~q~ rounds. In the ~i~-th round of the game, the robot will be placed on the field ~(a_i, b_i)~. The goal is to reach the field ~(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.

Input Specification

The first line contains integers ~n~, ~m~ and ~k~ ~(1 \le n, m \le 10^6, 0 \le k \le 10^5)~, the number of rows, columns and non-empty fields on the board.

The ~i~-th of the following ~n~ lines contains integers ~x_i~, ~y_i~ and character ~s_i~ ~(1 \le x_i \le n, 1 \le y_i \le m, s_i =~ L or ~s_i =~ R~)~, the row and column of ~i~-th turn field and the type of turn. If ~s_i =~ L then it is a left turn field. If ~s_i =~ R then it is a right turn field.

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

The ~i~-th of the following ~q~ lines contains 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)~, the starting position and the goal.

Output Specification

In the ~i~-th of the following ~q~ lines output the minimal number of turns for the ~i~-th round of the game or -1 if it is impossible to reach the goal.

Scoring

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

Explanation for Sample 2

First round: We start at ~(1, 1)~. If we direct the robot to the left, it will arrive at ~(1, 3)~ in the next step because it wanted to exit the board, so it wraps around to the other side. Field ~(1, 3)~ is a left turn field, so the robot is now directed downwards. After two more steps, it will be at the desired goal ~(3, 3)~.

Second round: We start at ~(3, 3)~. If we direct the robot upwards, it will arrive at ~(1, 3)~ in two steps, where it will be directed to the left due to the left turn field. After two steps, it will be at the field ~(1, 1)~, which is also a left turn field, so it will be directed downwards. In the next step, it will be at the desired goal ~(2, 1)~.

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

---