18253번 - 최단경로와 쿼리

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

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

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

• r₁ c₁ r₂ c₂ : r₁행 c₁열에서 r₂행 c₂열로 가는 경로 중 지나는 셀의 가중치 합의 최솟값을 출력하여라.

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

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

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

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

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

이후 Q개의 줄에 걸쳐 쿼리를 나타내는 4개의 정수 r₁, c₁, r₂, c₂ (1 ≤ r₁, r₂ ≤ N, 1 ≤ c₁, c₂ ≤ M)가 주어진다.

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