Maximal Square Tent

In the Nordic highlands, finding a reliable water source is a matter of life and death when camping. Traditionally, Nordic campers set up their tents directly on top of water sources so that water is always within reach. Interestingly, they only use square tents.

Jon is planning his new campsite. The campsite can be modeled as an \(N \times M\) grid, where each cell is either flat (available) or rugged (unavailable). Some regions have been marked as unusable.

For each water source given by its coordinates, determine the maximum side length of a square tent that can be placed on the grid such that:

• All cells within the square are available.
• The square covers the water source.

If no square tent can cover the water source, output 0.

Note: The grid cells are 1-indexed.

inputFormat

The input begins with two space-separated integers \(N\) and \(M\) (the dimensions of the grid).

Each of the next \(N\) lines contains \(M\) integers (either 0 or 1) separated by spaces. Here, 1 indicates an available (flat) cell and 0 indicates a rugged (unavailable) cell.

The next line contains an integer \(Q\), the number of water source queries.

Each of the following \(Q\) lines contains two integers \(r\) and \(c\), representing the 1-indexed row and column of a water source.

outputFormat

For each query, output a single integer on its own line, representing the maximum side length of a square tent that covers the water source.

sample

5 5
1 1 1 1 1
1 1 0 1 1
1 1 1 1 1
0 1 1 1 1
1 1 1 1 1
2
3 2
5 4

3
3