I. Square Jutsu!
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

After years of experimentation, Kakashi has come up with the "square"-jutsu, a powerful technique that strikes lightning onto a large square area of land. Kakashi happens to be testing his jutsu on a mountain, which can be modeled by an $$$N \times N$$$ grid.

Each cell at row $$$1\leq i\leq N$$$ and column $$$1\leq j\leq N$$$ on the mountain has an elevation $$$c_{i, j}$$$. For every cell $$$(i,j)$$$ it is guaranteed that $$$c_{i,j} \leq \min \left(c_{i+1, j}, \space c_{i, j+1}, \space c_{i+1, j+1}\right)$$$ (treating cells outside the $$$N\times N$$$ grid as having infinite elevation). It is also guaranteed that $$$c_{1, 1} = 0$$$.

Kakashi's jutsu is powerful, but limited: square-jutsu can strike any $$$k\times k$$$ square block of mountain cells, but only if the entire $$$k\times k$$$ block lies within the bounds of the mountain grid and only if every cell in the block has elevation within a certain range $$$[a, b]$$$ inclusive ($$$a \leq c_{i, j} \leq b$$$ for all cells $$$(i,j)$$$ in the target square). Given the elevation of every mountain cell and the elevation range allowed by his jutsu, Kakashi wants to know the number of cells in the largest possible square block his jutsu can hit.

Input

The first line of input contains 2 integers $$$N$$$ and $$$Q$$$ ($$$1 \leq N \leq 300, \space 1 \leq Q \leq 10^4$$$), the size of the grid and the number of test cases, respectively. Each test case uses the same mountain grid.

The next $$$N$$$ lines each contain $$$N$$$ space-separated integers. The $$$j$$$-th integer on the $$$i$$$-th line represents the elevation $$$c_{i, j}$$$ ($$$0 \leq c_{i, j} \leq N^2$$$).

The next $$$Q$$$ lines each specify one test case, and contain two space-separated integers $$$a$$$ and $$$b$$$ ($$$0 \leq a \leq b \lt N^2$$$), the minimum and maximum elevation that Kakashi's square-jutsu can hit.

Output

For each test case, print a line with one integer: the number of mountain cells in the largest square block of land that Kakashi's square-jutsu can strike. For each test case it is guaranteed that Kakashi can target at least one cell.

Examples
Input
5 5
0 1 2 3 4
0 1 2 4 4
0 2 3 5 6
1 3 3 5 6
1 4 4 6 7
6 7
4 4
0 6
3 4
5 7
Output
1
1
16
4
4
Input
10 5
0 0 0 0 0 0 1 2 3 3
1 1 1 1 1 1 2 2 3 4
1 2 2 2 2 2 3 3 3 4
2 2 2 2 2 2 3 3 3 5
2 2 2 3 3 3 3 3 3 6
3 3 3 3 3 3 4 5 5 7
4 4 4 4 5 5 6 6 6 7
4 4 5 5 5 5 7 7 7 8
5 5 6 6 6 6 8 8 9 9
5 5 6 6 6 6 8 8 10 11
4 6
2 3
3 11
3 6
2 5
Output
16
16
36
25
25
Input
4 1
0 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
0 15
Output
16