Phá game

Sau khi vô địch AFF Cup 2018, đội tuyển bóng đá Việt Nam được một doanh nghiệp thưởng nóng bằng trò chơi bảng chứa vàng. Trong trò chơi, mỗi cầu thủ phải di chuyển trên một bảng hình chữ nhật $m\times n$, các hàng được đánh số từ $1$ đến $m$ từ trên xuống dưới, các cột được đánh số từ $1$ đến $n$ từ trái qua phải. Ô ở hàng $i$ cột $j$ ghi số $a_{ij}$.

Mỗi cầu thủ được yêu cầu đi từ ô $(u,v)$ tới ô $(p,q)$ $(1\le u<p\le m;1\le v<q\le n)$. Tại mỗi bước, cầu thủ chỉ được đi từ trên xuống dưới hoặc từ trái sang phải qua các ô kề cạnh, cứ đi qua ô nào (tính cả ô xuất phát và ô kết thúc), cầu thủ được nhận số vàng bằng số ghi trong ô đó.

Các cầu thủ vốn rất thông minh và tìm ra cách đi để đạt được số vàng tối đa được thưởng, tuy nhiên có một cổ động viên đối phương do cay cú nên muốn phá game. Anh ta gây sự bằng cách nhảy vào bảng chiếm trọn một ô, trừ ô xuất phát $(u,v)$ và ô kết thúc $(p,q)$. Ô bị cổ động viên chiếm thì cầu thủ không được đi vào, do đó không lấy được vàng tương ứng với số ghi trong ô đó: cầu thủ phải chọn một đường đi khác không qua ô này.

Cổ động viên này muốn tìm một ô để ngồi chiếm sao cho trong chiến thuật tối ưu của mỗi cầu thủ, tổng số điểm lớn nhất có thể nhận được là tối thiểu.

Yêu cầu: Cho bảng $m\times n$ với các giá trị $|a_{ij}|<{10}^6$. Với $k$ lượt đi của các cầu thủ biểu diễn bởi $4$ số $u,v,p,q$. Hãy "an ủi" cổ động viên này bằng cách xác định tổng số vàng mà cầu thủ nhận được trong mỗi lượt nếu cổ động viên chọn được đúng ô tốt nhất có thể để chiếm theo mô tả trên. Các lượt đi độc lập với nhau: ở mỗi lượt cổ động viên chọn lại ô chiếm.

Dữ liệu vào

• Dòng đầu tiên chứa $3$ số nguyên $m,n,k$.
• $m$ dòng tiếp theo, dòng thứ $i$ chứa $n$ số nguyên $a_{i1},a_{i2},\dots ,a_{in}$.
• $k$ dòng cuối, mỗi dòng chứa $4$ số nguyên dương $u,v,p,q$ $(1\le u<p\le m;1\le v<q\le n)$.

Dữ liệu ra

Gồm $k$ dòng, dòng thứ $i$ chứa một số nguyên là số điểm mà cầu thủ nhận được ở lượt chơi thứ $i$ nếu cổ động viên xấu tính đó chọn được ô tốt nhất.

Ràng buộc

• $2\le m,n\le 300$; $1\le k\le 300$
• $|a_{ij}|<{10}^6$
• $1\le u<p\le m$; $1\le v<q\le n$

Subtasks

• Subtask 1 ($30\%$ số test): $m,n,k\le 30$;
• Subtask 2 ($30\%$ số test): $m,n,k\le 100$;
• Subtask 3 ($40\%$ số test): $m,n,k\le 300$.

Ví dụ