A6403 | 「USACO 2021.1 Platinum」Paint by Letters

**题目来自 [USACO 2021 January Contest, Platinum](http://usaco.org/index.php?page=jan21results) Problem 3. [Paint by Letters](http://usaco.org/index.php?page=viewproblem2&cpid=1094&lang=zh)。**

Bessie 最近收到了一套颜料。画布可以用一个 $N \times M$ 的矩形方阵表示，其中行从上往下编号为 $1 \sim N$，列从左往右编号为 $1 \sim M$（$1 \le N, M \le 1000$）。被涂色的方格的颜色可以用一个 A 到 Z 的大写字母表示。初始时，所有方格均未被涂色，每个方格至多只能被涂色一次。

Bessie 指定了每个方格她所希望的颜色。她一笔可以将一些组成连通分量的方格涂上颜色，也就是说这些方格之间可以通过相邻方格互相到达。如果两个方格有公共边则认为它们是相邻的。

例如，$3 \times 3$ 的画布

```plain
AAB
BBA
BBB
```

可以用如下四笔完成涂色：

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

使用少于四笔不可能得到最终结果。

作为一名先锋派艺术家，Bessie 只会对这个画布中的一个子矩形进行涂色。现在，她正在考虑 $Q$ 个候选子矩形（$1 \le Q \le 1000$），每一候选给定四个整数 $x_1$、$y_1$、$x_2$ 和 $y_2$ ，表示由第 $x_1$ 行到第 $x_2$ 行及第 $y_1$ 列到第 $y_2$ 列的所有方格组成的子矩形。

对于每个候选子矩形，将所有子矩形内的方格都涂上所希望的颜色，并且子矩形外的方格均不涂色，最少需要涂多少笔？注意在这个过程中 Bessie 并没有真正进行任何的涂色，所以对于每个候选的回答是独立的。

输入的第一行包含三个数 $N, M, Q$。

以下 $N$ 行每行包含一个由 $M$ 个大写字母组成的字符串，表示画布每行所希望的颜色。

以下 $Q$ 行每行包含四个空格分隔的整数 $x_1, y_1, x_2, y_2$，表示一个候选子矩形（$1 \le x_1 \le x_2 \le N$，$1 \le y_1 \le y_2 \le M$）。

对于 $Q$ 个候选子矩形的每一个，输出一行，包含答案。