Robots

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

At the start, the robot is placed on a field $(x, y)$ ($x$-th row, $y$-th column). The player can direct it in one of four directions: up, down, left, or right. The robot moves in the chosen direction until it reaches the goal or a special field. If it tries to leave the board, it wraps around to the opposite side. For example, if the robot is at $(n, 3)$ and moves down, it arrives at $(1, 3)$.

The board has three types of fields:

• Empty field: the robot keeps moving in the same direction.
• Left turn field: when the robot steps on it, the robot turns left by 90° and keeps moving.
• Right turn field: when the robot steps on it, the robot turns right by 90° and keeps moving.

Most fields are empty. Only $k$ fields are left or right turn fields.

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

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

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, the number of columns, and the number of non-empty fields on the board.

Each of the following $k$ lines contains integers $x_i$, $y_i$ and a character $s_i$ ($1 \le x_i \le n$, $1 \le y_i \le m$, $s_i$ is L or R). The pair $(x_i, y_i)$ is the row and column of the $i$-th turn field, and $s_i$ is its type. L is a left turn field and R is a right turn field.

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

Each 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 start and the goal of the round.

For each round, output the minimum number of turns on its own line, or -1 if the goal cannot be reached.