포도 덩굴

콰드라도니아(Quadradonia)의 모든 농지는 정사각형이고, 넓이가 모두 같으며, 완전히 평평하고, 각 변이 남북 방향과 동서 방향에 나란히 놓여 있다.

농지가 평평하기 때문에 콰드라도니아의 언덕은 높이가 서로 다른 거대한 계단처럼 보인다. 어느 산에는 $N \times M$개의 농지로 이루어진 흥미로운 직사각형 구역이 있다. 이 구역에서 임의의 농지에서 시작해 서쪽에서 동쪽으로 이동하면 높이가 비내림차순(non-decreasing)이다. 마찬가지로 임의의 농지에서 시작해 북쪽에서 남쪽으로 이동해도 높이가 비내림차순이다.

콰드라도니아의 한 대형 포도주 회사가 이 구역의 일부 농지를 빌려 포도를 재배하려고 한다. 이 회사는 특정 높이 구간에서 재배할 때에만 잘 자라는 특별한 포도 품종에 관심이 있다. 즉, 높이가 주어진 고도 $L$ 이상이고 $U$ 이하인 농지만 빌리려 한다. 수확을 쉽게 하기 위해 빌리는 농지들은 서로 연결된 하나의 구역을 이루어야 하며, 콰드라도니아 사람들은 정사각형을 좋아하므로 그 구역은 반드시 정사각형이어야 한다.

회사는 아직 어떤 품종을 재배할지 정하지 않았으므로, 품종마다 하나씩 높이 구간을 나타내는 질의 목록을 가지고 있다.

직사각형 관심 구역의 정보와 높이 구간 질의 목록이 주어질 때, 각 질의에 대해 높이가 모두 해당 구간 안에 있는, 서로 연결된 정사각형 구역의 가장 큰 한 변의 길이(농지 개수 단위)를 구하는 프로그램을 작성하여라. 예를 들어 $4 \times 5$ 크기의 관심 구역에서는 서로 다른 높이 구간에 대해 여러 가지 정사각형이 조건을 만족할 수 있다.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스의 첫 줄에는 공백 하나로 구분된 두 정수 $N$과 $M$이 주어지며, 각각 남북 방향 농지의 개수($1 \le N \le 500$)와 동서 방향 농지의 개수($1 \le M \le 500$)를 나타낸다. 이어지는 $N$개의 줄에는 각각 공백으로 구분된 $M$개의 정수 $H_{i,j}$가 주어지며, 이는 농지의 높이를 나타낸다($1 \le i \le N$, $1 \le j \le M$에 대해 $0 \le H_{i,j} \le 10^5$이고, 또한 $H_{i-1,j} \le H_{i,j}$, $H_{i,j-1} \le H_{i,j}$이다). 다음 줄에는 질의의 개수를 나타내는 정수 $Q$가 주어진다($1 \le Q \le 10^4$). 이어지는 $Q$개의 줄에는 각각 공백 하나로 구분된 두 정수 $L$과 $U$가 주어지며, 하나의 높이 구간을 나타낸다($0 \le L \le U \le 10^5$). 빌리는 농지의 높이는 $L$ 이상 $U$ 이하여야 한다.

마지막 테스트 케이스 다음에는 공백 하나로 구분된 두 개의 0이 담긴 줄이 주어지며, 이 줄은 처리하지 않는다.

각 테스트 케이스마다 $Q + 1$개의 줄을 출력한다. 처음 $Q$개의 줄에는 각각 하나의 정수를 출력하는데, 이는 해당 질의의 구간 안에 모든 높이가 포함되는, 서로 연결된 정사각형 구역의 가장 큰 한 변의 길이(농지 개수 단위)이다(그런 정사각형이 없으면 $0$을 출력한다). 각 테스트 케이스에서 마지막으로 출력하는 줄은 구분자로, 하이픈 문자 '-' 하나로만 이루어진다.