Tô Màu Theo Số

Cho một lưới $N\times M$ ô, mỗi ô được tô một trong 26 màu (chữ cái in hoa A–Z). Với mỗi truy vấn, bạn được cho một hình chữ nhật con của lưới, hãy đếm số vùng liên thông của các ô cùng màu trong hình chữ nhật đó.

Hai ô được coi là liền kề nếu chúng chia sẻ một cạnh chung. Một vùng liên thông là tập hợp tối đa các ô cùng màu mà có thể đi từ ô này sang ô kia chỉ qua các ô liền kề cùng màu.

Dữ liệu vào

• Dòng đầu: ba số nguyên $N$, $M$, $Q$.
• $N$ dòng tiếp theo: mỗi dòng là một xâu $M$ ký tự in hoa (màu của các ô trong hàng đó).
• $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$ — hình chữ nhật con từ hàng $x_1$, cột $y_1$ đến hàng $x_2$, cột $y_2$ (1-indexed, bao gồm cả hai đầu mút).

Dữ liệu ra

Với mỗi truy vấn, in ra số vùng liên thông trên một dòng riêng.

Ràng buộc

• $1\le N,M\le 1000$
• $1\le Q\le 1000$
• $1\le x_1\le x_2\le N$, $1\le y_1\le y_2\le M$

Ví dụ

Ghi chú

Giới hạn bộ nhớ: 512MB. Giới hạn thời gian cao hơn 50% so với thông thường.