시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 512 MB 112 23 16 23.529%

문제

N개의 행과 M개의 열로 이루어진 격자가 있다.

격자의 각 셀에는 가중치가 있다. ij열의 가중치를 Vi,j로 표기하자.

다음과 같은 쿼리가 Q개 주어진다:

  • r1 c1 r2 c2 : r1c1열에서 r2c2열로 가는 경로 중 지나는 셀의 가중치 합의 최솟값을 출력하여라.

쿼리에 대한 답을 구해보자.

단, 어떤 셀에서 한 번에 이동할 수 있는 셀은 상하좌우로 인접한 셀이다.

입력

첫 줄에 두 정수 N(1 ≤ N ≤ 5)과 M(1 ≤ M ≤ 100,000)이 주어진다.

i+1(1 ≤ i ≤ N)번째 줄에는 M개의 정수 Vi,1Vi,2, ..., Vi,M 이 주어진다. (0 ≤ Vi,j ≤ 1,000,000,000)

N+2번째 줄에 쿼리의 수를 나타내는 정수 Q(1 ≤ Q ≤ 100,000)가 주어진다.

이후 Q개의 줄에 걸쳐 쿼리를 나타내는 4개의 정수 r1, c1, r2, c2 (1 ≤ r1, r2 ≤ N, 1 ≤ c1, c2M)가 주어진다.

출력

쿼리에 대한 답을 한 줄에 하나씩 차례로 출력하여라.

예제 입력 1

3 5
1 3 2 4 5
1 1 2 3 1
5 4 3 2 1
3
1 1 3 5
2 2 3 3
3 3 3 3

예제 출력 1

10
6
3

출처

Contest > Good Bye, BOJ > Good Bye, BOJ 2019! G번