Wave

题目描述

波在不同的介质中的传播速度是不一样的。真空中波速都是 $3\times108m/s$，而在液体介质中的波速会比真空中的波速小，并且在不同的液体介质中波速不一样。我们将一个液体表面分成 $N \times M$ 块相同大小的正方形格子，每个格子中只包含一种液体介质。现在我们想知道，从某个波源传出去的波能以不变的波速延伸到多大的以波源为中心的大正方形内。假定所有大正方形的边都是平行于坐标轴的。

输入格式

输入文件第一行包含三个整数 $N$、$M$ 和 $Q$，分别表示液体表面分成的正方形格子的行数和列数，以及询问的个数。接下来是一个 $N \times M$ 的矩阵，其中每个元素包含一个小写字母表示相应各自内的介质，不同的字母表示不同的介质。接下来 $Q$ 行每行用两个数 $X$ 和 $Y$ 描述一个询问，表示询问以第 $X$ 行第 $Y$ 列为波源的波能以不变的波速延伸到的最大的以波源为中心的大正方形的边长。注意行的标号从 $0$ 到 $N-1$，列的标号从 $0$ 到 $M-1$。

输出格式

输出文件包括 $Q$ 行，每行包含一个整数，即相应问题的答案。

样例 #1

样例输入 #1

5 5 3
abbaa
abbaa
aaaaa
aaaaa
aaaaa
1 2
1 4
3 2

样例输出 #1

1
1
3

提示

对于 $30\%$ 的数据，有 $1 \le N,M \le 50$，$1 \le Q \le 500$；

对于 $100\%$ 的数据，有 $1 \le N,M \le 1000$，$1 \le Q \le 10000$。