EJOI là gì so với MixiLand?

DoMixi đang dẫn đội stream vào một mê cung khổng lồ. Mê cung gồm ~n \times m~ phòng xếp theo lưới, phòng góc trên bên trái là ~(1, 1)~, phòng góc dưới bên phải là ~(n, m)~. Giữa mỗi cặp phòng kề nhau có một cửa, được sơn một trong bốn màu: xanh dương (P), đỏ (C), xanh lá (Z) và cam (N).

Người anh em stream MixiGa biết đường ra nhưng hắn ta chỉ chỉ đường nếu DoMixi trả lời được các câu hỏi của hắn.

Câu hỏi của MixiGa: "Nếu chúng ta đang ở phòng ~(a_i, b_i)~ và đích đến là phòng ~(c_i, d_i)~, thì cần đi qua tối thiểu bao nhiêu màu cửa khác nhau để đến đó?"

DoMixi đang bận cười với chat, nhờ bạn giúp trả lời ~q~ câu hỏi của MixiGa!

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên ~n~ và ~m~ (~1 \le n, m \le 100~, ~1 < n \times m~) — số hàng và cột của mê cung.

~n~ dòng tiếp theo, mỗi dòng chứa ~m-1~ ký tự (P, C, Z hoặc N) — màu cửa nối phòng ~(i,j)~ với ~(i,j+1)~.

~n-1~ dòng tiếp theo, mỗi dòng chứa ~m~ ký tự — màu cửa nối phòng ~(i,j)~ với ~(i+1,j)~.

Dòng tiếp theo chứa số nguyên ~q~ (~1 \le q \le 100~) — số câu hỏi.

~q~ dòng cuối, mỗi dòng chứa bốn số nguyên ~a_i, b_i, c_i, d_i~ (~1 \le a_i, c_i \le n~, ~1 \le b_i, d_i \le m~, ~(a_i,b_i) \ne (c_i,d_i)~).

Kết quả

Với mỗi câu hỏi, in ra số màu cửa khác nhau tối thiểu cần đi qua trên một dòng.

Ví dụ

Đầu vào 1:

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

Đầu ra 1:

4
2
3
1

Đầu vào 2:

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

Đầu ra 2:

1
2
1
3

Giới hạn