### 问题描述 小齐最近收到了一套绘画工具。画布可以被表示为一个 $N \times M$ 的矩形，其中行从上到下标记为 $1…N$，列从左到右标记为 $1…M$（$1 \leq N, M \leq 1000$）。一旦上色，每个单元格的颜色可以用大写字母 $A$ 到 $Z$ 表示。最初，所有单元格都未上色，一个单元格不能被涂色多次。 小齐已经指定了她对每个单元格的颜色的期望。她可以用一笔绘制一组相邻的单元格，如果该组形成一个连通分量，这意味着该组中的任何单元格都可以通过一系列相邻的单元格到达任何其他单元格。两个单元格被认为是相邻的，如果它们共享一条边。 作为一位前卫的艺术家，小齐最终只会绘制画布的一个子矩形。目前，她正在考虑 $Q$ 个候选区域，每个都可以用四个整数 $x_1, y_1, x_2, y_2$ 表示。这意味着子矩形包含所有行范围在 $x_1$ 到 $x_2$（包括 $x_1, x_2$）之间，列范围在 $y_1$ 到 $y_2$（包括 $y_1, y_2$）之间的所有单元格。 对于每个候选子矩形，绘制每个单元格的期望颜色的最小笔画次数是多少，同时将子矩形外的所有单元格保持未上色？请注意，小齐在此过程中实际上不进行任何绘画，因此每个候选的答案是独立的。 ### 输入格式 第一行包含三个整数 $N, M, Q$。 接下来的 $N$ 行，每行包含一个包含 $M$ 个大写字母的字符串，表示画布每行上的期望颜色。 接下来的 $Q$ 行，每行包含四个由空格分隔的整数 $x_1, y_1, x_2, y_2$，表示一个候选子矩形（$1 \leq x_1 \leq x_2 \leq N, 1 \leq y_1 \leq y_2 \leq M$）。 ### 输出格式 对于每个候选子矩形，输出一个新行，表示答案。 ### 样例输入 ``` 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 ``` ### 评测数据规模 $1 \leq Q \leq 1000$。