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

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

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

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

산은 하늘에서 봤을 때 높이가 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

이번에는 등산 timer 1s memory 256MB

이번에는 등산 1s 256MB