Theo bạn, EJOI là gì?

Là phòng game!

Teo đang tìm kiếm đội EJOI của Croatia. Cô ấy đã tìm thấy Gabriel, nhưng còn Vito, Dino và Ivo.

Teo và đội EJOI đang ở trong một mê cung gồm ~n \times m~ phòng, tất cả đều có cùng kích thước. Các phòng tạo thành một mạng lưới. Phòng phía trên bên trái được gán nhãn ~(1, 1)~ và phòng phía dưới bên phải được gán nhãn ~(n, m)~. Giữa mỗi cặp phòng liền kề có một cửa được tô màu bằng một trong bốn màu: xanh lam (được đánh dấu bằng kí tự P), đỏ (được đánh dấu bằng kí tự C), xanh lục (được đánh dấu bằng kí tự Z) và màu cam (được đánh dấu bằng kí tự N).

Tại một thời điểm nào đó, Gabriel nói: Tôi biết những người còn lại trong nhóm ở đâu, nhưng tôi sẽ chỉ cho bạn biết nếu bạn có thể trả lời tất cả các câu hỏi của tôi.

Câu hỏi của Gabriel là: Nếu chúng ta hiện đang ở trong phòng ~(a_i, b_i)~ và những người còn lại trong đội đang ở trong phòng ~(c_i, d_i)~, thì số lượng cửa tối thiểu mà chúng ta phải đi qua để đến được với họ là bao nhiêu?

Teo rất giỏi trả lời các câu hỏi của Gabriel, nhưng đơn giản là có quá nhiều câu hỏi. Cô ấy không có nhiều thời gian (xe buýt sắp khởi hành), vì vậy cô ấy đang nhờ bạn trả lời giúp cô ấy câu hỏi của Gabriel!

Input

• Dòng đầu tiên chứa hai số nguyên dương ~n~ và ~m~ (~1 \leq n, m \leq 100, 1 < n \times m~).
• Dòng thứ ~i~ trong ~n~ dòng tiếp theo chứa ~m-1~ kí tự (P, C, Z hoặc N), kí tự thứ ~j~ thể hiện màu của cửa giữa phòng ~(i,j)~ và phòng ~(i,j+1)~.
• Dòng thứ ~i~ trong ~n-1~ dòng tiếp theo chứa ~m~ kí tự (P, C, Z hoặc N), kí tự thứ ~j~ thể hiện màu của cửa giữa phòng ~(i,j)~ và phòng ~(i+1,j)~.
• Dòng tiếp theo chứa số nguyên dương ~q~ (~q \leq 100~).
• Dòng thứ ~i~ trong ~q~ dòng tiếp theo chứa bốn số nguyên dương ~a_i, b_i, c_i, d_i~ (~1 \leq a_i, c_i \leq n, 1 \leq b_i, d_i \leq m, (a_i, b_i) \neq (c_i, d_i)~), mô tả câu hỏi của Gabriel.

Output

Dòng thứ ~i~ trong ~q~ dòng là câu trả lời cho câu hỏi thứ ~i~ của Gabriel.

Scoring

1. ~n=1~ (11 điểm)

2. Các cửa nối phòng ~(i,j)~ và phòng ~(i,j+1)~ đều có màu xanh lam, các cửa nối phòng ~(i,j)~ và phòng ~(i+1,j)~ đều có màu đỏ (13 điểm)

3. Mọi cửa đều có màu đỏ hoặc xanh lam (24 điểm)

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

Sample Input 1

1 8
CPZNCCP
4
1 1 1 8
1 3 1 5
1 8 1 4
1 2 1 3

Sample Output 1

4
2
3
1

Sample Input 2

3 3
PP
PP
PP
CCC
CCC
3
1 1 3 3
3 3 2 2
1 1 1 3

Sample Output 2

2
2
1

Sample Input 3

4 4
CCC
CPC
PPP
CNP
ZZZZ
PPPP
CPZC
4
3 1 2 3
1 1 4 4
2 2 3 3
1 4 4 1

Sample Output 3

1
2
1
3

Explanation

Ở ví dụ thứ ba, với câu hỏi đầu tiên, Teo và Gabriel chỉ cần sử dụng cánh cửa màu xanh lam để tiếp cận những người còn lại trong đội; với câu hỏi thứ hai, họ có thể sử dụng cửa màu xanh lam và xanh lục; ở câu hỏi thứ ba chỉ cần màu xanh là đủ; và với câu hỏi thứ tư, họ có thể sử dụng cửa màu xanh lam, xanh lục và đỏ.