Robots Game

Kile is a board game enthusiast who discovered a game called Robots. The game is played on an \(n \times m\) grid together with a robot. The grid cells are addressed with \((1,1)\) as the top‐left corner and \((n,m)\) as the bottom–right corner.

At the beginning, the robot is placed at some cell \((x,y)\) (i.e. row \(x\), column \(y\)). The player may choose one of the four directions (up, down, left, right) to move the robot. Once a direction is chosen, the robot moves continuously in that direction until it either enters the target cell or a special cell. Note that if at any point the robot moves off the grid, it will wrap around to the opposite side. For example, if it is at \((n,3)\) and moves downwards, it will appear at \((1,3)\).

The grid contains three types of cells:

• Empty cell: The robot simply continues in the same direction.
• Left-turn cell: When the robot enters this cell, it immediately turns left by \(90^\circ\) and continues moving.
• Right-turn cell: When the robot enters this cell, it immediately turns right by \(90^\circ\) and continues moving.

Most cells are empty, and there are only \(k\) special cells (either left-turn or right-turn) on the board. The game has \(q\) rounds. In the \(i\)th round, the robot is placed at a starting cell \((a_i,b_i)\) and the goal is to reach the target cell \((c_i,d_i)\) using the minimum number of turns. If it is impossible to reach the target, output \(-1\).

Note: If the starting cell or the target cell is a turning cell, the turning effect of that cell is ignored.

inputFormat

The first line contains four space‐separated integers \(n, m, k, q\) representing the dimensions of the grid, the number of special cells, and the number of rounds respectively.

The following \(k\) lines each contain two integers and a character: \(x\) \(y\) \(t\), where \((x,y)\) is the position of a special cell and \(t\) is either 'L' (for left-turn) or 'R' (for right-turn).

Each of the next \(q\) lines contains four integers \(a_i\), \(b_i\), \(c_i\), \(d_i\) describing the starting cell and target cell for that round.

outputFormat

For each round, output a single line containing the minimum number of turns needed to reach the target cell from the starting cell, or \(-1\) if it is impossible.

sample

3 3 2 3
2 2 L
3 2 R
1 1 3 3
2 1 3 3
1 2 3 2

-1
2
0