Cho ma trận kích thước \(n×m\), ô trái trên có tọa độ ~(1,1)~ và ô phải dưới có tọa độ ~(n,m)~. Ban đầu, Robot được đặt tại ô ~(x,y)~ và được định hướng di chuyển lên, xuống, trái hoặc phải. Robot tiếp tục di chuyển cho đến khi đến đích hoặc đi vào một ô đặc biệt. Nếu bước di chuyển tiếp theo Robot sắp ra khỏi ma trận thì tự động nhảy sang phía đối diện, ví dụ tại ô ~(n,3)~ và di chuyển xuống dưới sẽ đến ô ~(1,3)~.

Ma trận có tổng cộng ~k~ ô đặc biệt thuộc một trong hai dạng:

• Ô rẽ trái: Hướng của Robot quay trái \(90°\) khi đi vào ô này.
• Ô rẽ phải: Hướng của Robot quay phải \(90°\) khi đi vào ô này.

Bạn phải trả lời ~q~ câu hỏi, mỗi câu hỏi bao gồm bốn số nguyên ~a_i,b_i,c_i,d_i~, yêu cầu đặt Robot tại vị trí ~(a_i,b_i)~ và chọn hướng đi ban đầu sao cho Robot đến được ô ~(c_i,d_i)~ với số lần thay đổi hướng ít nhất có thể ~(~lưu ý rằng chỉ có thể chọn hướng đi cho Robot một lần duy nhất~)~.

Lưu ý rằng nếu Robot bắt đầu hoặc kết thúc tại ô đặc biệt thì việc thay đổi hướng không được tính.

Input

• Dòng đầu tiên chứa ba số nguyên ~n~, ~m~ và ~k~ ~(1 \le n,m \le 10^6; \; 0 \le k \le 10^5)~.
• ~k~ dòng tiếp theo, dòng thứ ~i~ bao gồm hai số nguyên ~x_i~, ~y_i~ ~(1 \le x_i \le n; \; 1 \le y_i \le m)~ là tọa độ của ô đặc biệt và một ký tự ~s_i~ ~(s_i \in \{L,R\})~ với ~s_i=L~ là ô rẽ trái và ~s_i=R~ là ô rẽ phải.
• Dòng tiếp theo chứa số nguyên ~q~ ~(1 \le q \le 3.10^5)~.
• ~q~ dòng tiếp theo, dòng thứ ~i~ chứa bốn số nguyên ~a_i~, ~b_i~, ~c_i~ và ~d_i~ ~(1 \le a_i,c_i \le n; \; 1 \le b_i,d_i \le m)~.

Output

• In ra ~q~ dòng, dòng thứ ~i~ là số lần đổi hướng ít nhất của Robot, hoặc in ra ~-1~ nếu không thể đến được ô đích.

Samples

Sample Input 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

Sample Output 1

-1
1
0
0
0

Sample Input 2

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

Sample Output 2

1
2
1
1
1
0
3

Sample Input 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

Sample Output 3

2
1
1
0
-1
5
0

Scoring

• Subtask ~1~ với ~25\%~ số điểm: ~k=0~
• Subtask ~2~ với ~25\%~ số điểm: ~n,m \le 300; \; q \le 10~
• Subtask ~3~ với ~25\%~ số điểm: ~n,m \le 300~
• Subtask ~4~ với ~25\%~ số điểm: Không còn ràng buộc gì thêm

Clarification

Trong ví dụ thứ hai,

• Ở câu hỏi đầu tiên, Robot được đặt ở vị trí ~(1,1)~. Nếu ban đầu định hướng Robot di chuyển sang trái, Robot sẽ đến ô ~(1,3)~ ở bước di chuyển đầu tiên. Ô ~(1,3)~ là ô rẽ trái, vì vậy sau khi đi vào ô này thì Robot sẽ di chuyển xuống. Sau hai bước di chuyển tiếp theo, Robot sẽ đến được ô ~(3,3)~.
• Ở câu hỏi thứ hai, Robot bắt đầu từ ô ~(3,3)~. Nếu định hướng Robot di chuyển lên trên, sau hai bước Robot sẽ đến ô ~(1,3)~ và Robot sẽ di chuyển sang trái vì ô ~(1,3)~ là ô rẽ trái. Sau hai bước tiếp theo, Robot đến được ô ~(1,1)~ cũng là một ô rẽ trái, vì vậy Robot di chuyển xuống dưới. Sau bước di chuyển tiếp theo, Robot đến được ô ~(2,1)~.