시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB50719414843.023%

문제

N×N의 행렬이 있다(1 ≤ N ≤ 250). 행렬의 각 성분은 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개의 줄에, 차례로 각 질문의 답변(부분행렬의 최댓값과 최솟값의 차이값)을 출력한다.

예제 입력 1

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

예제 출력 1

5
W3sicHJvYmxlbV9pZCI6IjE5OTkiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWNkNWNcdWIzMDBcdWNkNWNcdWMxOGMiLCJkZXNjcmlwdGlvbiI6IjxwPk4mdGltZXM7Tlx1Yzc1OCBcdWQ1ODlcdWI4MmNcdWM3NzQgXHVjNzg4XHViMmU0KDEgJmxlOyBOICZsZTsgMjUwKS4gXHVkNTg5XHViODJjXHVjNzU4IFx1YWMwMSBcdWMxMzFcdWJkODRcdWM3NDAgMjUwXHViY2Y0XHViMmU0IFx1Yzc5MVx1YWM3MFx1YjA5OCBcdWFjMTlcdWM3NDAgXHVjNzRjXHVjNzc0IFx1YzU0NFx1YjJjYyBcdWM4MTVcdWMyMThcdWM3NzRcdWIyZTQuIFx1YjJmOVx1YzJlMFx1YzVkMFx1YWM4Y1x1YjI5NCBLKDEgJmxlOyBLICZsZTsgMTAwLDAwMClcdWFjMWNcdWM3NTggXHVjOWM4XHViYjM4XHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhYzAxIFx1YzljOFx1YmIzOFx1Yzc0MCwgXHVjOGZjXHVjNWI0XHVjOWM0IFx1ZDU4OVx1YjgyY1x1Yzc1OCBCJnRpbWVzO0IgXHVkMDZjXHVhZTMwXHVjNzU4IFx1YmQ4MFx1YmQ4NFx1ZDU4OVx1YjgyY1x1Yzc1OCZuYnNwO1x1Y2Q1Y1x1YjMxM1x1YWMxMlx1YWNmYyBcdWNkNWNcdWMxOWZcdWFjMTJcdWM3NTggXHVjYzI4XHVjNzc0XHViOTdjIFx1YmIzYlx1YjI5NCBcdWM5YzhcdWJiMzhcdWI0ZTRcdWM3NzRcdWIyZTQoMSAmbGU7IEIgJmxlOyBOKS4gXHVhYzAxIFx1YzljOFx1YmIzOFx1YzVkMCBcdWIzMDBcdWQ1NzRcdWMxMWMsIFx1YmQ4MFx1YmQ4NFx1ZDU4OVx1YjgyY1x1Yzc1OCBcdWFjMDBcdWM3YTUgXHVjNjdjXHVjYWJkIFx1YzcwNFx1Yzc1OCBcdWM3MDRcdWNlNThcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWMwXHViYTcwLCBcdWJhYThcdWI0ZTAgXHVjOWM4XHViYjM4XHViNGU0XHVjNzQwIFx1YWMxOVx1Yzc0MCBCXHVhYzEyXHVjNzQ0IFx1YWMxNlx1YjI5NFx1YjJlNC4gXHVjOWM4XHViYjM4XHVjNWQwIFx1YjJmNVx1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWMxMzggXHVjODE1XHVjMjE4IE4sIEIsIEtcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWIyZTRcdWM3NGMgTlx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVkNTg5XHViODJjXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjYzI4XHViODQwXHViODVjIDFcdWQ1ODksIDJcdWQ1ODksICZoZWxsaXA7LCBOXHVkNTg5XHVjNzc0IFx1YjQxY1x1YjJlNC4gXHVhYzAxIFx1YzkwNFx1YzVkMFx1YjI5NCBOXHVhYzFjXHVjNzU4IFx1YzgxNVx1YzIxOFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWJhNzAsIFx1Yzc3NFx1YjI5NCBcdWNjMjhcdWI4NDBcdWI4NWMgMVx1YzVmNFx1Yzc1OCBcdWMxMzFcdWJkODQsIDJcdWM1ZjRcdWM3NTggXHVjMTMxXHViZDg0LCAmaGVsbGlwOywgTlx1YzVmNFx1Yzc1OCBcdWMxMzFcdWJkODRcdWM3NzQgXHViNDFjXHViMmU0LiBcdWIyZTRcdWM3NGMgS1x1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjOWM4XHViYjM4XHViNGU0XHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhYzAxIFx1YzljOFx1YmIzOFx1YjRlNFx1Yzc0MCBcdWI0NTAgXHVjODE1XHVjMjE4IGksIGpcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBpXHViMjk0IFx1YmQ4MFx1YmQ4NFx1ZDU4OVx1YjgyY1x1Yzc1OCBcdWFjMDBcdWM3YTUgXHVjNzE3XHVjYWJkXHVjNzU4IFx1ZDU4OSBcdWJjODhcdWQ2MzhcdWM3NzRcdWJhNzAsIGpcdWIyOTQgXHViZDgwXHViZDg0XHVkNTg5XHViODJjXHVjNzU4IFx1YWMwMFx1YzdhNSBcdWM2N2NcdWNhYmRcdWM3NTggXHVjNWY0IFx1YmM4OFx1ZDYzOFx1Yzc3NFx1YjJlNCgxICZsZTsgaSwgaiAmbGU7IE4tQisxKTxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPktcdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwLCBcdWNjMjhcdWI4NDBcdWI4NWMgXHVhYzAxIFx1YzljOFx1YmIzOFx1Yzc1OCBcdWIyZjVcdWJjYzAoXHViZDgwXHViZDg0XHVkNTg5XHViODJjXHVjNzU4IFx1Y2Q1Y1x1YjMxM1x1YWMxMlx1YWNmYyBcdWNkNWNcdWMxOWZcdWFjMTJcdWM3NTggXHVjYzI4XHVjNzc0XHVhYzEyKVx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMTk5OSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkNvcm5maWVsZHMiLCJkZXNjcmlwdGlvbiI6IjxwPkZKIGhhcyBkZWNpZGVkIHRvIGdyb3cgaGlzIG93biBjb3JuIGh5YnJpZCBpbiBvcmRlciB0byBoZWxwIHRoZSBjb3dzIG1ha2UgdGhlIGJlc3QgcG9zc2libGUgbWlsay4gJm5ic3A7VG8gdGhhdCBlbmQsIGhlJiMzOTtzIGxvb2tpbmcgdG8gYnVpbGQgdGhlIGNvcm5maWVsZCBvbiB0aGUgZmxhdHRlc3QgcGllY2Ugb2YgbGFuZCBoZSBjYW4gZmluZC48XC9wPlxyXG5cclxuPHA+RkogaGFzLCBhdCBncmVhdCBleHBlbnNlLCBzdXJ2ZXllZCBoaXMgc3F1YXJlIGZhcm0gb2YgTiB4IE4gaGVjdGFyZXMgKDEgJmx0Oz0gTiAmbHQ7PSAyNTApLiBFYWNoIGhlY3RhcmUgaGFzIGFuIGludGVnZXIgZWxldmF0aW9uICgwICZsdDs9IGVsZXZhdGlvbiAmbHQ7PSAyNTApIGFzc29jaWF0ZWQgd2l0aCBpdC48XC9wPlxyXG5cclxuPHA+Rkogd2lsbCBwcmVzZW50IHlvdXIgcHJvZ3JhbSB3aXRoIHRoZSBlbGV2YXRpb25zIGFuZCBhIHNldCBvZiBLICgxICZsdDs9IEsgJmx0Oz0gMTAwLDAwMCkgcXVlcmllcyBvZiB0aGUgZm9ybSAmcXVvdDtpbiB0aGlzIEIgeCBCIHN1Ym1hdHJpeCwgd2hhdCBpcyB0aGUgbWF4aW11bSBhbmQgbWluaW11bSBlbGV2YXRpb24/JnF1b3Q7LiAmbmJzcDtUaGUgaW50ZWdlciBCICgxICZsdDs9IEIgJmx0Oz0gTikgaXMgdGhlIHNpemUgb2Ygb25lIGVkZ2Ugb2YgdGhlIHNxdWFyZSBjb3JuZmllbGQgYW5kIGlzIGEgY29uc3RhbnQgZm9yIGV2ZXJ5IGlucXVpcnkuIEhlbHAgRkogZmluZCB0aGUgYmVzdCBwbGFjZSB0byBwdXQgaGlzIGNvcm5maWVsZC48XC9wPlxyXG4iLCJpbnB1dCI6Ijx1bD5cclxuXHQ8bGk+TGluZSAxOiBUaHJlZSBzcGFjZS1zZXBhcmF0ZWQgaW50ZWdlcnM6IE4sIEIsIGFuZCBLLjxcL2xpPlxyXG5cdDxsaT5MaW5lcyAyLi5OKzE6IEVhY2ggbGluZSBjb250YWlucyBOIHNwYWNlLXNlcGFyYXRlZCBpbnRlZ2Vycy4gJm5ic3A7TGluZSAyIHJlcHJlc2VudHMgcm93IDE7IGxpbmUgMyByZXByZXNlbnRzIHJvdyAyLCBldGMuICZuYnNwO1RoZSBmaXJzdCBpbnRlZ2VyIG9uIGVhY2ggbGluZSByZXByZXNlbnRzIGNvbHVtbiAxOyB0aGUgc2Vjb25kIGludGVnZXIgcmVwcmVzZW50cyBjb2x1bW4gMjsgZXRjLjxcL2xpPlxyXG5cdDxsaT5MaW5lcyBOKzIuLk4rSysxOiBFYWNoIGxpbmUgY29udGFpbnMgdHdvIHNwYWNlLXNlcGFyYXRlZCBpbnRlZ2VycyByZXByZXNlbnRpbmcgYSBxdWVyeS4gVGhlIGZpcnN0IGludGVnZXIgaXMgdGhlIHRvcCByb3cgb2YgdGhlIHF1ZXJ5OyB0aGUgc2Vjb25kIGludGVnZXIgaXMgdGhlIGxlZnQgY29sdW1uIG9mIHRoZSBxdWVyeS4mbmJzcDsgVGhlIGludGVnZXJzIGFyZSBpbiB0aGUgcmFuZ2UgMS4uTi1CKzEuPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJvdXRwdXQiOiI8dWw+XHJcblx0PGxpPkxpbmVzIDEuLks6IEEgc2luZ2xlIGludGVnZXIgcGVyIGxpbmUgcmVwcmVzZW50aW5nIHRoZSBkaWZmZXJlbmNlIGJldHdlZW4gdGhlIG1heCBhbmQgdGhlIG1pbiBpbiBlYWNoIHF1ZXJ5LjxcL2xpPlxyXG48XC91bD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==