In Quadradonia, all rural properties are square, all have the same area, all are perfectly flat and all have the sides aligned to the North-South and West-East axes. Since properties are flat, the hills in Quadradonia look like a series of huge stairs’ steps, with different heights. In a certain mountain, an interesting situation occurs in a rectangular area of \(N \times M\) properties. Starting from anywhere within the region, traversing it in the West to East direction, the properties have non-descending heights. Similarly, traversing that region in the North to South direction, starting from anywhere, the properties have also non-descending heights.

A large wine company in Quadradonia wants to rent some properties from that region to grow wine grapes. The company is interested in some special varieties of wine grapes, which are productive only if grown in properties that are square whose heights are within a certain interval. That is, the company is interested in renting properties whose heights are equal to or higher than a given altitude \(L\), and equal to or lower than a given altitude \(U\). To make it easier for harvesting, the rented properties must form a contiguous area. And since everyone in Quadradonia likes squares, the area to be rented must have the shape of a square.

The company has not yet decided which variety of grapes it will grow, and therefore it has a list of queries involving intervals, one for each grape variety. You must write a program that, given the description of the rectangular area of interest in the mountain, and a list of queries containing height intervals, determines, for each query, the largest side, in number of properties, of a contiguous square area with heights within the specified interval.


The input contains several test cases. The first line of a test case contains two integers \(N\) and \(M\), separated by a single space, that represent the number of properties in the North-South (\(1 \leq N \leq 500\)) direction and the number of properties in the West-East direction (\(1 \leq M \leq 500\)), respectively. Each of the next \(N\) lines contains \(M\) integers \(H_{i,j}\), separated by single spaces, indicating the heights of the properties in the region of interest (\(0 \leq H_{i,j} \leq 10^5\), for \(1 \leq i \leq N\) and \(1 \leq j \leq M\); also, \(H_{i-1,j} \leq H_{i,j}\) and \(H_{i,j-1} \leq H_{i,j}\)). The next line contains an integer \(1 \leq Q \leq 10^4\) indicating the number of queries. Each of the next \(Q\) lines describes a query, and contains two integers \(0 \leq L\leq U \leq 10^5\), separated by a single space, indicating one interval of heights. The heights of properties to be rented must be greater than or equal to \(L\) and less than or equal to \(U\).

The last test case is followed by a line containing two zeros separated by a single space.


For each test case in the input your program must print \(Q+1\) lines. Each of the first \(Q\) lines must contain a single integer, indicating the largest side, in number of properties, of a contiguous square area with heights within the interval specified in the respective input query. The last line to be printed for each test case is used as a separator and must contain a single character '-' (known as hyphen or minus sign).

Sample Input

4 5
13 21 25 33 34
16 21 33 35 35
16 33 33 45 50
23 51 66 83 93
22 90
33 35
20 100
4 4
1 7 9 11
5 8 10 12
7 10 15 17
11 19 30 41
6 20
7 9
10 10
13 14
0 0

Sample Output


This is challenge 12192 of the ACM International Collegiate Programming Contest. Test input is provided by uDebug.

Upload Solution

Please log in to submit your solution.


Difficulty (1 vote)
Average test runtime 0.46
Points (changes over time) 10
Tried by 5 users
Solved by 5 users

Global ranking

# Name Runtime Points worth
1 ,s/java/NaN/gi 0.15 16
2 贝尔恩德 0.16 15
3 Pascal 0.16 15
4 Mac 0.71 3
5 AlexanderP 1.11 2