페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#7075
서브태스크

Roboti 2초 1024MB

문제

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° and continue moving

  • Right turn field - when the robot steps on this field, it will turn right by 90° 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.


입력

The first line contains integers n,m and k (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 n lines contains integers x_i, y_i and character s_i (1 ≤ x_i ≤ n, 1 ≤ y_i ≤ 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 integer q (1 ≤ q ≤ 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 ≤ a_i , c_i ≤ n, 1 ≤ b_i , d_i ≤ m), the starting position and the goal.


출력

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.


부분문제

번호 점수 조건
#110점

 k = 0 

#213점

 n, m ≤ 300, q ≤ 10 

#349점

 n, m ≤ 300

#438점

No additional constraints.


예제1

입력
222
11L
22R
5
1122
2112
1112
2111
2221
출력
-1
1
0
0
0

예제2

입력
334
11L
13L
21L
33L
7
1133
3321
3122
2312
2331
1232
3322
출력
1
2
1
1
1
0
3

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).


예제3

입력
448
11R
13L
22R
24L
31L
33L
42L
44L
7
1214
2234
4432
4144
4231
1223
2423
출력
2
1
1
0
-1
5
0

출처

COCI 2023/2024 Contest #4 5번

역링크