dungde99 vừa vẽ ra một bảng số nguyên dương gồm ~M~ hàng và ~N~ cột, các hàng được đánh số từ ~1~ đến ~M~ từ trên xuống và các cột được đánh số từ ~1~ đến ~N~ từ trái sang phải. dungde99 ký hiệu ô ~(i, j)~ là ô nằm ở giao điểm của hàng ~i~ và cột ~j~ của bảng. Sau đó, dungde99 đưa ra bộ bốn số ~x_1~, ~y_1~, ~x_2~ và ~y_2~ rồi đố Flow God tìm một đường đi tối ưu từ ô ~\left(x_1, y_1\right)~ đến ô ~\left(x_2, y_2\right)~, tức là một đường đi xuất phát tại ô ~\left(x_1, y_1\right)~ mà tại mỗi bước Flow God chỉ có thể di chuyển sang ô kề bên phải hoặc ô kề bên dưới của ô hiện tại, đồng thời tổng các số ghi ở các ô trên đường đi (bao gồm cả ô ~\left(x_2, y_2\right)~) phải nhỏ nhất có thể. Flow God nhanh chóng trả lời được câu đố đầu tiên của dungde99 nhưng sau đó dungde99 lại hỏi tiếp hàng loạt câu hỏi dạng tương tự như vậy khiến Flow God phải bó tay trong sự lúng túng. Các bạn hãy giúp Flow God giải đáp tất cả các câu đố này nhé!

Input

Dòng đầu chứa hai số nguyên dương ~M~ và ~N~ ~(1\leq M, N\leq 100)~.

~M~ dòng sau, mỗi dòng chứa ~N~ số nguyên dương mô tả một hàng ngang của bảng. Các số này có giá trị không vượt quá ~10^6~.

Dòng tiếp theo chứa số nguyên dương ~Q~.

~Q~ dòng sau, mỗi dòng chứa bốn số nguyên dương ~x_1~, ~y_1~, ~x_2~ và ~y_2~ mô tả một truy vấn đường đi tối ưu từ ô ~\left(x_1, y_1\right)~ đến ô ~\left(x_2, y_2\right)~ trong bảng ~\left(1\leq x_1\leq x_2\leq M, 1\leq y_1\leq y_2\leq N\right)~.

Output

Gồm ~Q~ dòng, mỗi dòng chứa một số nguyên là tổng các số trên đường đi tối ưu tương ứng.

Ví dụ

Input

4 5
1 2 3 4 5
5 4 3 2 1
2 4 6 8 10
11 9 5 3 7
2
1 1 3 3
1 2 4 5

Output

14
26

Ràng buộc

• Subtask 1 (30 điểm): ~Q\leq 10^6~ và tất cả các số ghi trong bảng đều bằng ~1~.
• Subtask 2 (30 điểm): ~Q\leq 10^4~.
• Subtask 3 (40 điểm): ~Q\leq 10^6~.