Cho một bảng gồm \(m\) hàng và \(n\) cột. Ô ở hàng \(i\), cột \(j\) chứa số nguyên dương \(a_{i,j}\).

Bạn cần trả lời \(q\) truy vấn. Mỗi truy vấn cho hai ô \((x_1,y_1)\) và \((x_2,y_2)\), trong đó \(x_1 \le x_2\) và \(y_1 \le y_2\). Từ một ô, bạn chỉ có thể đi sang ô kề bên phải hoặc ô kề bên dưới. Khi đi vào ô \((i,j)\), bạn phải trả chi phí \(a_{i,j}\).

Với mỗi truy vấn, hãy tìm tổng chi phí nhỏ nhất để đi từ \((x_1,y_1)\) đến \((x_2,y_2)\). Chi phí của ô xuất phát không được tính; chi phí của mọi ô đi vào sau đó, bao gồm ô đích, đều được tính.

Input

• Dòng đầu tiên chứa hai số nguyên \(m,n\).
• \(m\) dòng tiếp theo, mỗi dòng chứa \(n\) số nguyên; số thứ \(j\) trên dòng thứ \(i\) là \(a_{i,j}\).
• Dòng tiếp theo chứa số nguyên \(q\).
• Mỗi trong \(q\) dòng tiếp theo chứa bốn số nguyên \(x_1,y_1,x_2,y_2\), mô tả một truy vấn.

Output

Với mỗi truy vấn, in ra trên một dòng tổng chi phí nhỏ nhất tìm được.

Constraints

• \(1 \le m,n \le 100\).
• \(1 \le a_{i,j} \le 10^6\).
• \(1 \le q \le 10^6\).
• \(1 \le x_1 \le x_2 \le m\).
• \(1 \le y_1 \le y_2 \le n\).

Scoring

• Subtask 1 (\(30\%\) số điểm): \(a_{i,j}=1\) với mọi ô.
• Subtask 2 (\(30\%\) số điểm): \(q \le 10^4\).
• Subtask 3 (\(40\%\) số điểm): Không có ràng buộc gì thêm.

Example

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

9
7
3