Bessie vừa được tặng một bộ dụng cụ vẽ. Tấm vải được biểu diễn bằng một hình chữ nhật \(N\times M\) ô, với các hàng đánh số \(1\ldots N\) từ trên xuống và các cột đánh số \(1\ldots M\) từ trái sang phải (\(1\le N,M\le1000\)). Sau khi tô, màu của mỗi ô được biểu diễn bằng một chữ cái in hoa từ A đến Z. Ban đầu mọi ô đều chưa có màu và mỗi ô không được tô quá một lần.

Bessie đã chỉ định màu mong muốn cho từng ô. Trong một nét cọ, cô có thể tô một tập ô bằng cùng một màu nếu tập đó tạo thành một thành phần liên thông, tức từ một ô bất kỳ trong tập có thể đi tới mọi ô khác qua một dãy ô kề. Hai ô được coi là kề nhau nếu có chung một cạnh.

Ví dụ, tấm vải \(3\times3\) sau:

AAB
BBA
BBB

có thể được tô bằng bốn nét như sau, và không thể dùng ít hơn:

...    ..B    AAB    AAB    AAB
... -> ... -> ... -> BB. -> BBA
...    ...    ...    BBB    BBB

Là một nghệ sĩ tiên phong, Bessie sẽ chỉ tô một hình chữ nhật con của tấm vải. Cô đang xét \(Q\) ứng viên (\(1\le Q\le1000\)), mỗi ứng viên được mô tả bởi bốn số nguyên \(x_1,y_1,x_2,y_2\). Hình chữ nhật con gồm mọi ô có hàng từ \(x_1\) đến \(x_2\) và cột từ \(y_1\) đến \(y_2\), kể cả hai đầu.

Với mỗi hình chữ nhật con ứng viên, hãy tính số nét cọ ít nhất để tô mỗi ô bên trong đúng màu mong muốn, đồng thời giữ mọi ô bên ngoài chưa tô. Bessie không thực sự tô trong quá trình này, nên đáp án của các ứng viên độc lập với nhau.

Lưu ý: Giới hạn thời gian của bài cao hơn mức mặc định 50%, và giới hạn bộ nhớ là 512 MB, gấp đôi mức mặc định.

Dữ liệu vào

Dòng đầu tiên chứa \(N\), \(M\) và \(Q\).

\(N\) dòng tiếp theo, mỗi dòng chứa một xâu gồm \(M\) chữ cái in hoa, biểu diễn màu mong muốn của một hàng trên tấm vải.

\(Q\) dòng tiếp theo, mỗi dòng chứa bốn số nguyên \(x_1,y_1,x_2,y_2\), cách nhau bởi dấu cách, mô tả một hình chữ nhật con ứng viên (\(1\le x_1\le x_2\le N\), \(1\le y_1\le y_2\le M\)).

Dữ liệu ra

Với mỗi ứng viên trong \(Q\) ứng viên, in đáp án trên một dòng mới.

Phân nhóm

• Các test 1-2 thỏa mãn \(N,M\le50\).
• Trong các test 3-5, tấm vải không chứa chu trình đơn sắc. Cụ thể, không tồn tại một dãy ô phân biệt \(c_1,c_2,c_3,\ldots,c_k\) thỏa mãn đồng thời:
• \(k>2\);
• mọi ô \(c_1,\ldots,c_k\) có cùng màu mong muốn;
• \(c_i\) kề \(c_{i+1}\) với mọi \(1\le i<k\);
• \(c_k\) kề \(c_1\).
• Trong các test 6-8, mỗi thành phần liên thông gồm các ô có cùng màu mong muốn có thể nằm trọn trong một hình vuông \(2\times2\) có cạnh song song với các trục tọa độ.
• Trong các test 9-11, mỗi thành phần liên thông như vậy có thể nằm trọn trong một hình vuông \(3\times3\) có cạnh song song với các trục tọa độ.
• Các test 12-20 không có ràng buộc bổ sung.

Tấm vải \(3\times3\) ở trên có một chu trình đơn sắc là bốn ô B ở góc dưới bên trái. Nó không thỏa mãn điều kiện của các test 6-8 vì thành phần gồm năm ô B không nằm trọn trong hình vuông \(2\times2\). Tấm vải \(3\times3\) này thỏa mãn điều kiện của các test 9-11.

Ví dụ

4 8 9
ABBAAAAA
ABAAAABA
CAADABBA
AAAAAAAA
1 1 4 8
3 5 3 8
1 3 2 4
1 4 2 5
1 1 3 3
4 4 4 4
2 6 4 8
3 5 4 6
1 6 3 8

6
3
2
1
4
1
3
2
2

Nguồn

USACO 2021 January Contest, Platinum - Paint by Letters: https://usaco.org/index.php?page=viewproblem2&cpid=1094

Tác giả: Andi Qu.