Kile, một người đam mê board game, gần đây đã phát hiện ra trò chơi Robots. Trò chơi bao gồm một bảng ~n \times m~ và một robot. Ô ~(1, 1)~ là ô trên cùng bên trái của bảng và ô ~(n, m)~ là ô dưới cùng bên phải.

Lúc đầu, robot được định vị trên một số ô ~(x, y)~ và người chơi có thể điều khiển nó theo một trong bốn hướng: lên, xuống, trái hoặc phải. Tùy thuộc vào hướng đã chọn, nó sẽ di chuyển theo hướng đó cho đến khi gặp mục tiêu hoặc một ô đặc biệt trên bảng. Nếu tại bất kỳ thời điểm nào nó muốn thoát khỏi bảng, nó sẽ vòng sang phía bên kia. Ví dụ: nếu nó nằm ở ô ~(n, 3)~ và muốn di chuyển xuống dưới thì nó sẽ đến ô ~(1, 3)~.

Bảng có ba loại ô:

• Ô trống - robot có thể tiếp tục di chuyển theo hướng hiện tại.
• Ô quay trái - khi robot bước đến ô này, nó sẽ quay trái ~90^\circ~ và tiếp tục di chuyển.
• Ô quay phải - khi robot bước đến ô này, nó sẽ quay phải ~90^\circ~ và tiếp tục di chuyển.

Hầu hết các ô trong bảng đều trống, chỉ có ~k~ trong số chúng là ô quay trái hoặc ô quay phải.

Trò chơi gồm ~q~ vòng. Ở vòng thứ ~i~, robot sẽ được đặt trên ô ~(a_i, b_i)~. Mục tiêu là đến được ô ~(c_i, d_i)~ bằng cách sử dụng số lượt quay tối thiểu hoặc xác định rằng điều đó là không thể.

Sau khi chơi trò chơi nhiều lần, Kile nhận ra rằng nó thử thách hơn so với thoạt nhìn ban đầu. Đó là lí do anh ấy cần bạn giúp đỡ. Hãy giúp anh ấy đưa ra số lần đổi hướng ít nhát cho mỗi vòng trò chơi.

Lưu ý: nếu robot bắt đầu hay kết thúc ở ô quay trái hay quay phải, lần quay đó không được tính.

Input

• Dòng đầu tiên chứa các số nguyên ~n~, ~m~ và ~k~ ~(1 \leq n, m \leq 10^6,~ ~0 \leq k \leq 10^5)~ là số hàng, số cột và số ô khác ô trống trên bảng.
• Dòng thứ ~i~ trong ~n~ dòng tiếp theo gồm hai số nguyên ~x_i~, ~y_i~ và kí tự ~s_i~ ~(1 \leq x_i \leq n,~ ~1 \leq y_i \leq m,~ ~s_i = ~L hoặc ~s_i=~R~)~, là tọa độ của ô quay đó. Nếu ~s_i=~L thì đó là ô quay trái. Nếu ~s_i=~R thì đó là ô quay phải.
• Dòng tiếp theo chứa số nguyên ~q~ ~(1 \leq q \leq 3 \times 10^5)~ là số vòng.
• Dòng thứ ~i~ trong ~q~ dòng tiếp theo chứa các số nguyên ~a_i, b_i, c_i, d_i~ ~(1 \leq a_i, c_i \leq n,~ ~1 \leq b_i, d_i \leq m)~ là vị trí bắt đầu và vị trí đích.

Output

Ở dòng thứ ~i~ trong ~q~ dòng đưa ra số lần quay ít nhất ở vòng thứ ~i~ của trò chơi hoặc đưa ra ~-1~ nếu không thể đến được ô đích.

Scoring

1. ~k=0~ (10 điểm)

2. ~n, m \leq 300, q \leq 10~ (13 điểm)

3. ~n, m \leq 300~ (49 điểm)

4. Không có ràng buộc gì thêm (38 điểm)

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

Explanation

Ở ví dụ thứ hai:

• Vòng đầu tiên: bắt đầu ở ~(1,1)~; khi điều hướng robot sang bên trái, nó sẽ đến ~(1,3)~ ở bước tiếp theo vì nó muốn ra khỏi bảng, nên nó quay vòng sang bên đối diện; ô ~(1,3)~ là ô quay trái, nên robot sẽ hướng xuống; sau hai bước, nó sẽ đến được ô đích.
• Vòng thứ hai: bắt đầu ở ~(3,3)~; khi điều hướng robot lên trên, nó sẽ đến ~(1,3)~ trong hai bước, sau đó quay hướng sang trái vì đó là ô quay trái; sau hai bước, nó đến ô ~(1,1)~, sau đó quay hướng xuống dưới vì đó là ô quay trái; bước tiếp theo nó đến được ô đích.