Mê cung có kích thước n × m, được chia thành n × m phòng có kích thước 1 × 1, giữa các phòng có các bức từng ngăn cách. Có thể xem mê cung như một ma trận phòng, phòng ở góc phía trên bên trái được gán nhãn (1, 1) và phòng ở góc phía dưới bên phải có được gán nhãn (n, m). Giữa các cặp phòng liền kề có một bức tường có 1 trong 4 màu: xanh lam (kí tự P), đỏ (kí tự C), xanh lá cây (kí tự Z) hoặc cam (kí tự N).

Hình minh hoạ là mê cung trong test 3. Căn phòng nơi Hải đang ở đánh đánh dấu bằng một chấm tròn màu đen, còn căn phòng Dương đang ở được đánh dấu bằng chấm tròn màu trắng. Một con đường từ Hải đến Dương được đánh dấu bằng màu xám đi qua các cánh cửa với 3 màu khác nhau (Đỏ, xanh lam, xanh lá cây – C, P, Z).

Có q câu hỏi, mỗi câu hỏi có dạng: Nếu Hải đang ở một phòng có nhãn (a_i, b_i) và Dương đang ở trong phòng có nhãn là (c_i, d_i), thì Hải cần phải đi qua tối thiểu bao nhiêu màu cửa để đến được chỗ của Dương.

Dữ liệu vào:

• Dòng đầu tiên chưa 2 số nguyên dương n, m (1 ≤ n, m ≤ 100, 1 < n × m) là kích thước của mê cung.

• Dòng thứ i trong n dòng tiếp theo, mỗi dòng chứa m-1 kí tự (P, C, Z hoặc N) trong đó chữ cái thứ j biểu thị màu cửa nối các phòng (i, j) và (i, j+1).

• Dòng thứ i trong n-1 dòng tiếp theo, mỗi dòng chứa m kí tự (P, C, Z hoặc N), trong đó chữ cái thứ j biểu thị màu cửa nối phòng (i, j) và (i+1, j).

• Dòng tiếp theo là số nguyên dương q (1 ≤ q ≤ 100) là số câu hỏi

• q dòng tiếp theo mỗi dòng chứa 4 số nguyên a_i, b_i, c_i, d_i là thông tin của một câu hỏi. Dữ liệu các câu hỏi đảm bảo đôi một khác nhau.

Kết quả:

• Gồm q dòng, dòng thứ i viết câu trả lời tương ứng cho câu hỏi thứ i trong dữ liệu.

Ràng buộc:

• 15% số điểm có n = 1

• 15% số điểm có tất cả các cửa nối các phòng (i, j) và (i, j+1) có màu xanh lam và tất cả các cửa nối các phòng (i, j) và (i+1, j) đều có màu đỏ.

• 30% số điểm có tất cả các cửa sẽ có màu xanh hoặc đỏ

• 40% số điểm còn lại không có ràng buộc gì thêm.

Ví dụ: