이번에는 등산

신나고 즐거운 정올 캠프 시기가 돌아왔다!

그런데 원장님은 충격적이게도 이번엔 축구가 아닌 등산을 하자고 하신다.

여러분은 높은 산을 오르기를 원치 않았지만 등산을 피할 수는 없었기에, 최대한 낮게 이동하는 등산로를 찾으려 한다.

여기서 "최대한 낮게"란, 등산로가 지나치는 모든 칸의 높이 중 최대치가 최소가 되도록 하는 등산로이다. 이를 등산로를 지나는 최소 높이라고 하자.

산은 하늘에서 봤을 때 높이가 M, 너비가 N인 직사각형으로 표현할 수 있다. 그리고 각 칸에는 해당 위치의 산의 높이인 h가 기록되어 있다.

산에서는 상하좌우로만 이동할 수 있고, 등산이기 때문에 산 밖으로는 이동할 수 없다.

원장님이 생각하는 Q가지 시작점과 끝점에 대해 등산로를 지나는 최소 높이를 구해보자!

<제한조건>

1 ≤ M, N ≤ 500

1 ≤ Q ≤ 100,000

1 ≤ h ≤ 1,000,000

1 ≤ x1, x2 ≤ M

1 ≤ y1, y2 ≤ N

입력

첫 줄에 세 정수 M, N, Q가 띄어쓰기로 구분되어 입력된다.

이후 M개의 줄 동안, 각 줄에 N개의 정수가 입력된다.

각 정수는 해당 위치의 산의 높이인 h이다.

이후 Q개의 줄에, 시작점과 끝점 x1, y1, x2, y2가 띄어쓰기로 구분되어 입력된다.

이는 산의 (x1, y1) 위치에서 (x2, y2) 위치로 가는 등산로라는 뜻이다.

출력

Q줄에 걸쳐 (x1, y1)에서 (x2, y2)로 가는 등산로를 지나는 최소 높이를 출력한다.

부분문제

번호	점수	조건
#1	20점	1 ≤ M, N, Q ≤ 100
#2	80점	추가적인 제한이 없다.

예제

힌트

태그

이번에는 등산 1s 256MB