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. Lưu ý các ô nằm ngoài hình chữ nhật con không được dùng để nối các vùng bên trong.

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$, mô tả 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ụ