Description

Bessie has recently received a set of paints. The canvas can be represented as an $N \times M$ rectangular grid, where rows are numbered from top to bottom as $1 \ldots N$, and columns are numbered from left to right as $1 \ldots M$ ($1 \le N, M \le 1000$). The color of a painted cell can be represented by an uppercase letter from A to Z. Initially, all cells are unpainted, and each cell can be painted at most once.

Bessie specifies the desired color for every cell. In one stroke, she can paint some cells that form a connected component, meaning that these cells can reach each other through adjacent cells. Two cells are considered adjacent if they share a common edge.

For example, the $3 \times 3$ canvas

AAB
BBA
BBB

can be painted in the following four strokes:

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

It is impossible to obtain the final result using fewer than four strokes.

As an avant-garde artist, Bessie will only paint one sub-rectangle of this canvas. She is now considering $Q$ candidate sub-rectangles ($1 \le Q \le 1000$). Each candidate is given by four integers $x_1$, $y_1$, $x_2$, and $y_2$, representing the sub-rectangle consisting of all cells from row $x_1$ to row $x_2$ and from column $y_1$ to column $y_2$.

For each candidate sub-rectangle, if all cells inside the sub-rectangle are painted to their desired colors and all cells outside the sub-rectangle remain unpainted, what is the minimum number of strokes needed? Note that Bessie does not actually paint anything during this process, so the answer for each candidate is independent.

Note: For this problem, the time limit for each test point is $1.5$ times the default, and the memory limit is $2$ times the default, i.e. $512\text{MB}$.

Input Format

The first line contains $N$, $M$, and $Q$.

The next $N$ lines each contain a string of $M$ uppercase letters, representing the desired colors for each row of the canvas.

The next $Q$ lines each contain four space-separated integers $x_1, y_1, x_2, y_2$, representing a candidate sub-rectangle ($1 \le x_1 \le x_2 \le N$, $1 \le y_1 \le y_2 \le M$).

Output Format

For each of the $Q$ candidate sub-rectangles, output one line containing the answer.

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

Hint

Sample 1 Explanation

The first candidate consists of the entire canvas, and it can be painted in six strokes.

The desired colors of the second candidate sub-rectangle are

ABBA

and it can be painted in three strokes. Note that although when considering the entire canvas, cells $(3,5)$ and $(3,8)$ can be painted with color $A$ in one stroke, this is not the case when considering only the cells inside the sub-rectangle.

Test Point Properties

• Test points 1-2 satisfy $N, M \le 50$.
• In test points 3-5, the canvas does not contain a cycle made up of a single color. That is, there does not exist a sequence of distinct cells $c_1, c_2, c_3, \ldots, c_k$ satisfying the following conditions:
  • $k > 2$.
  • All of $c_1, \ldots, c_k$ have the same color.
  • For all $1 \le i < k$, $c_i$ is adjacent to $c_i+1$.
  • $c_k$ is adjacent to $c_1$. Note that the $3 \times 3$ canvas in the description contains a cycle made up of a single color (the four B cells in the lower-left corner).
• In test points 6-8, every connected component of cells with the same desired color can be contained within an axis-aligned $2 \times 2$ square. The $3 \times 3$ canvas in the description does not satisfy this property (the connected component of five B cells cannot be contained within a $2 \times 2$ square).
• In test points 9-11, every connected component of cells with the same desired color can be contained within an axis-aligned $3 \times 3$ square. The $3 \times 3$ canvas in the description satisfies this property.
• Test points 12-20 have no additional constraints.

Problem provided by: Andi Qu.

Translated by ChatGPT 5