Grapevine

In Quadradonia, all rural properties are square, all have the same area, all are perfectly flat, and all have their sides aligned with the North-South and West-East axes.

Because the properties are flat, the hills of Quadradonia look like a series of enormous staircase steps of differing heights. On one particular mountain there is an interesting rectangular region of $N \times M$ properties. Starting from any property and moving from West to East, the heights are non-decreasing. Likewise, starting from any property and moving from North to South, the heights are also non-decreasing.

A large wine company in Quadradonia wants to rent some properties in this region to grow wine grapes. The company is interested in special grape varieties that are productive only when grown on properties whose heights lie within a certain interval. That is, the company wants to rent properties whose heights are at least a given altitude $L$ and at most a given altitude $U$. To make harvesting easier, the rented properties must form a contiguous area, and, because everyone in Quadradonia loves squares, that area must be a square.

The company has not yet decided which variety it will grow, so it has a list of queries, one per grape variety, each describing a height interval.

Write a program that, given the description of the rectangular region of interest and a list of height-interval queries, determines for each query the largest possible side, measured in number of properties, of a contiguous square area whose heights all lie within the specified interval. For example, in a $4 \times 5$ region of interest, several different squares may satisfy different height intervals.

The input contains several test cases. The first line of each test case contains two integers $N$ and $M$ separated by a single space, giving respectively the number of properties in the North-South direction ($1 \le N \le 500$) and in the West-East direction ($1 \le M \le 500$). Each of the next $N$ lines contains $M$ integers $H_{i,j}$ separated by single spaces, giving the heights of the properties (for $1 \le i \le N$ and $1 \le j \le M$, $0 \le H_{i,j} \le 10^5$; moreover $H_{i-1,j} \le H_{i,j}$ and $H_{i,j-1} \le H_{i,j}$). The next line contains an integer $Q$, the number of queries ($1 \le Q \le 10^4$). Each of the next $Q$ lines contains two integers $L$ and $U$ separated by a single space, describing one height interval ($0 \le L \le U \le 10^5$); the heights of the rented properties must be at least $L$ and at most $U$.

The last test case is followed by a line containing two zeros separated by a single space, which must not be processed.

For each test case, print $Q + 1$ lines. Each of the first $Q$ lines must contain a single integer: the largest side, in number of properties, of a contiguous square area whose heights all lie within the interval of the corresponding query (print $0$ if no such square exists). The last line printed for each test case is a separator consisting of a single hyphen character '-'.