Description

The propagation speed of waves differs across media. In vacuum, all wave speeds are $3\times {10}^8$ m/s, while in liquid media the wave speed is lower than in vacuum and also varies between different liquid media. We divide a liquid surface into an $N \times M$ grid of equal-sized square cells, each cell containing exactly one liquid medium. We want to know, for a wave emitted from some source, how large an axis-aligned square centered at the source the wave can extend to while maintaining an unchanged wave speed. Assume all such squares are axis-aligned with the coordinate axes.

Input Format

The first line contains three integers $N, M, Q$, denoting the number of rows and columns of the grid and the number of queries, respectively. Then follows an $N \times M$ matrix in which each element is a lowercase letter representing the medium in the corresponding cell; different letters denote different media. Then follow $Q$ lines, each with two integers $X$ and $Y$ describing a query: the side length of the largest axis-aligned square centered at row $X$, column $Y$ within which the wave can extend while maintaining an unchanged wave speed is requested. Rows are numbered from $0$ to $N-1$, and columns from $0$ to $M-1$.

Output Format

Output $Q$ lines, each containing one integer, the answer to the corresponding query.

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

1
1
3

Hint

For $30\%$ of the testdata, $1 \le N, M \le 50$, $1 \le Q \le 500$.

For $100\%$ of the testdata, $1 \le N, M \le 1000$, $1 \le Q \le 10000$.

Translated by ChatGPT 5