Background

Translated from COCI 2023/2024 Contest #4 T5 “Roboti”.

Problem Description

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

At the beginning, the robot is at some position $(x, y)$ (row $x$, column $y$), and the player can move it in one of four directions: up, down, left, or right. Depending on the chosen direction, it will move in that direction until it reaches the target cell or a special cell in the grid. If at any time the robot tries to leave the board, it wraps around to the other side. For example, if it is at position $(n, 3)$ and wants to move down, it will arrive at position $(1, 3)$.

There are three types of cells on the board:

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

Most cells in the grid are empty; only $k$ cells are left-turn or right-turn cells.

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

After playing this game many times, Kile realized it is more challenging than it first appears. That is why he now needs your help. Help him determine the minimum number of turns needed for each round!

Note: If the start or end of the robot’s path is on a left-turn or right-turn cell, then that cell has no effect.

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, the number of columns, and the number of non-empty cells in the grid.

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, then it is a left-turn cell. If it is R, then it is a right-turn cell.

The next line contains one integer $q\ (1\le q\le 3\cdot 10^5)$, representing the number of 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 start and target positions.

Output Format

Output $q$ lines. On line $i$, output the minimum number of turns needed in round $i$. If the target cannot be reached, output $-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
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

Hint

Sample Explanation 2

Round 1: Start from $(1, 1)$. If the robot initially moves left, it will reach $(1, 3)$ in the next step, because it tries to leave the board and therefore enters from the other side. Position $(1, 3)$ is a left-turn cell, so the robot will move downward. After two more steps, it reaches the target position $(3, 3)$.

Round 2: Start from $(3, 3)$. If the robot initially moves up, it will reach $(1, 3)$ after two steps, where it turns left because of the left-turn cell. After two more steps, it reaches position $(1, 1)$, which is also a left-turn cell, so it will move downward. In the next step, it reaches the target position $(2, 1)$.

Subtasks

Translated by ChatGPT 5