시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 31 11 10 58.824%

문제

N×N의 행렬이 있다(1≤N≤250). 행렬의 각 성분은 정수이다(0≤성분≤250). 당신에게는 K(1≤K≤100,000)개의 질문이 주어진다. 각 질문은, 주어진 행렬의 B×B 크기의 부분행렬의  최대값과 최소값의 차이를 묻는 질문들이다(1≤B≤N). 각 질문에 대해서, 부분행렬의 가장 왼쪽 위의 위치가 주어지며, 모든 질문들은 같은 B값을 갖는다. 질문에 답하는 프로그램을 작성하시오.

입력

첫째 줄에는 세 정수 N, B, K가 주어진다. 다음 N개의 줄에는 행렬이 주어진다. 차례로 1행, 2행, …, N행이 된다. 각 줄에는 N개의 정수가 주어지며, 이는 차례로 1열의 성분, 2열의 성분, …, N열의 성분이 된다. 다음 K개의 줄에는 질문들이 주어진다. 각 질문들은 두 정수 i, j로 주어진다. i는 부분행렬의 가장 윗쪽의 행 번호이며, j는 부분행렬의 가장 왼쪽의 열 번호이다(1≤i, j≤N-B+1)

출력

K개의 줄에, 차례로 각 질문의 답변(부분행렬의 최대값과 최소값의 차이값)을 출력한다.

예제 입력

5 3 1
5 1 2 6 3
1 3 5 2 7
7 2 4 6 1
9 9 8 6 5
0 6 9 3 9
1 2

예제 출력

5

힌트