로봇

보드 게임을 좋아하는 케일은 최근 Robots라는 게임을 알게 되었다. 이 게임은 $n$행 $m$열 보드와 로봇 한 대로 진행한다. 칸 $(1, 1)$은 보드의 왼쪽 위이고, 칸 $(n, m)$은 오른쪽 아래다.

처음에 로봇은 칸 $(x, y)$ ($x$행 $y$열)에 놓인다. 플레이어는 위, 아래, 왼쪽, 오른쪽 중 한 방향으로 로봇을 보낼 수 있다. 로봇은 선택한 방향으로 목표 칸이나 특수 칸을 만날 때까지 움직인다. 보드 밖으로 나가려 하면 반대편으로 이어진다. 예를 들어 로봇이 칸 $(n, 3)$에서 아래로 움직이면 칸 $(1, 3)$에 도착한다.

보드의 칸은 세 종류다.

• 빈 칸: 로봇이 같은 방향으로 계속 움직인다.
• 왼쪽 회전 칸: 로봇이 이 칸에 들어서면 왼쪽으로 90° 회전하고 계속 움직인다.
• 오른쪽 회전 칸: 로봇이 이 칸에 들어서면 오른쪽으로 90° 회전하고 계속 움직인다.

대부분의 칸은 빈 칸이다. 왼쪽 회전 칸과 오른쪽 회전 칸은 합쳐서 $k$개뿐이다.

게임은 $q$라운드로 진행된다. $i$번째 라운드에서 로봇은 칸 $(a_i, b_i)$에 놓인다. 목표는 최소 회전 수로 칸 $(c_i, d_i)$에 도달하는 것이다. 도달할 수 없다면 그 사실을 판정한다.

참고: 로봇이 회전 칸에서 출발하거나 회전 칸에 도착하는 경우, 그 회전은 세지 않는다.

첫 줄에 정수 $n$, $m$, $k$ ($1 \le n, m \le 10^6$, $0 \le k \le 10^5$)가 주어진다. 각각 행의 수, 열의 수, 보드에서 빈 칸이 아닌 칸의 수다.

다음 $k$개의 줄에는 정수 $x_i$, $y_i$와 문자 $s_i$ ($1 \le x_i \le n$, $1 \le y_i \le m$, $s_i$는 L 또는 R)가 주어진다. $(x_i, y_i)$는 $i$번째 회전 칸의 행과 열이고, $s_i$는 그 칸의 종류다. L은 왼쪽 회전 칸, R은 오른쪽 회전 칸이다.

다음 줄에는 라운드 수 정수 $q$ ($1 \le q \le 3 \cdot 10^5$)가 주어진다.

다음 $q$개의 줄에는 정수 $a_i$, $b_i$, $c_i$, $d_i$ ($1 \le a_i, c_i \le n$, $1 \le b_i, d_i \le m$)가 주어진다. 각각 그 라운드의 출발 칸과 목표 칸이다.

각 라운드마다 최소 회전 수를 한 줄에 출력한다. 목표에 도달할 수 없으면 -1을 출력한다.