SPOJ Brasil

Na Quadradônia, todas as propriedades rurais são quadradas, todas possuem a mesma área, todas são perfeitamente planas e todas possuem os lados alinhados aos eixos Norte-Sul e Leste-Oeste.

Como as propriedades são planas, as colinas na Quadradônia parecem uma série de degrais gigantes, com tamanhos diferentes. Em uma certa montanha, uma situação interessante ocorre em uma área retangular de N x M propriedades. Começando de qualquer lugar da região, ao ir do Oeste para o Leste, as propriedades possuem alturas não-decrescentes. De forma simular, atravessar a região do Norte para o Sul, começando em qualquer lugar, as propriedades também possuem alturas não-decrescentes.

Uma grande empresa de vinhos na Quadradônia quer alugar algumas propriedades daquela região para cultivar uvas. A empresa está interessada em uma variedade especial de parreiras que só produzem uvas se cultivadas em propriedades cujas alturas estão em um certo intervalo. Ou seja, a empresa está interessada em alugar propriedades cujas alturas sejam maiores ou iguals a uma dada altura L e menores ou iguais a outra dada altura U. Para facilitar a colheita, as propriedades devem formar uma área contígua. E como todos na Quadradônia gostam de quadrados, a área a ser alugada deve ter a forma de um quadrado.

A empresa ainda não decidiu qual variedade de uvas irá produzir, e portanto possui uma lista de consultas envolvendo intervalos, um para cada variedade de uva. A figura abaixo mostra uma área de interesse de dimensão 4 x 5 (em número de propriedades) com exemplos de áreas que a empresa poderia alugar para cultivar uvas em alturas dentro dos intervalos dados nas figuras.

Intervalo=[20,90]	Intervalo=[33,35]	Intervalo=[20,100]

Você deve escrever um programa que, dadas a descrição da área de interesse na montanha e uma lista de consultas contendo intervalos de alturas, determina, para cada consulta, o maior lado (em número de propriedades) da maior área contígua quadrada com alturas dentro do intervalo em questão.

Entrada

A entrada contém vários casos de teste. A primeira linha de um caso de teste contém dois inteiros N e M, separados por um espaço simples, representando, respectivamente, o número de propriedades na direção Norte-Sul (1 ≤ N ≤ 500) e o número de propriedades na direção Oeste-Leste (1 ≤ M ≤ 500) da região de interesse. Cada uma das próximas N linhas contém M inteiros H_i,j, separados por espaços simples, indicando as alturas das propriedades na região de interesse (0 ≤ H_i,j ≤ 10⁵, com 1 ≤ i ≤ N e 1 ≤ j ≤ M; também, H_i-1,j ≤ H_i,j e H_i,j-1 ≤ H_i,j). A próxima linha contém um inteiro Q indicando o número de consultas (1 ≤ Q ≤ 10⁴). Cada uma das próximas Q linhas descrevem uma consulta e contém dois inteiros L e U, separados por um espaço em branco, indicando um intervalo de alturas (0 ≤ L ≤ U ≤ 10⁵). As alturas das propriedades a serem alugadas devem ser maiores ou iguais a L e menores ou iguais a U.

O último caso de teste é seguido de uma linha contendo dois zeros separados por um espaço simples.

Saída

Para cada caso de teste da entrada, seu programa deve imprimir Q+1 linhas. Cada uma das primeiras Q linhas deve conter um único inteiro, indicando o maior tamanho, em número de propriedades, de uma área quadrada contígua com alturas dentro do intervalo especificado na respectiva consulta. A última linha a ser impressa para cada caso de teste é usada como separadora e deve conter um único caractere '-' (conhecido como hífen ou "sinal de menos").

Exemplo

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

Saída:
3
2
4
-
3
1
1
0
-