Xét bảng số \(A\) có kích thước \(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 sang phải, ô giao giữa hàng \(i\) và cột \(j\) là ô \((i, j)\) có giá trị là \(a_{i, j}\). Một đường đi trong bảng là một dãy các ô, sao cho hai ô liên tiếp có chung cạnh, trọng số của đường đi là tổng của các ô trong dãy.
Bạn phải trả lời \(q\) truy vẫn. Trong mỗi truy vấn, bạn được cung cấp tọa độ của hai ô \((x, y)\) và \((u, v)\), Bạn phải tìm và đưa ra trọng số nhỏ nhất trong các đường đi từ ô \((x, y)\) đến ô \((u, v)\).

Input

• Dòng thứ nhất chứa hai số nguyên dương \(m, n\) \((1 \leq m \leq 7, 1 \leq n \leq 5000)\).
• Tiếp theo là \(m\) dòng, dòng thứ \(i\) chứa \(n\) số nguyên không âm \(a_{i, 1}, a_{i, 2}, \ldots, a_{i, n}\) \((1 \leq a_{i,j} \leq 123456)\).
• Dòng tiếp theo chứa số nguyên dương \(Q\) \((1 \leq Q \leq 300000)\).
• Dòng thứ \(t\) trong \(Q\) dòng tiếp theo, mỗi dòng chứa bốn số nguyên dương \(x_{t}, y_{t}, u_{t}, v_{t}\) \((1 \leq x_{t}, u_{t} \leq m, 1 \leq u_{t}, v_{t} \leq n)\)

Output

• Ghi ra \(Q\) dòng, dòng thứ \(t\) chứa một số nguyên là kết quả của truy vấn thứ \(t\).

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(n, Q \leq 500\).
• Subtask \(2\) (\(30\%\) số điểm): \(m = 2\).
• Subtask \(3\) (\(20\%\) số điểm): \(n \leq 500\).
• Subtask \(4\) (\(30\%\) số điểm): không có rằng buộc gì thêm.

Example

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

5
9

3 5
1 1 9 1 1
9 1 9 1 9
1 1 1 1 1
2
1 1 1 5
1 5 3 5

9
5