Cho một bảng số kích thước \(N \times N\). Có \(Q\) truy vấn, mỗi truy vấn yêu cầu tính tổng các số nằm trong hình chữ nhật con được xác định bởi góc trái trên \((x_1, y_1)\) và góc phải dưới \((x_2, y_2)\).

Input

• Dòng 1: Hai số nguyên \(N\) và \(Q\) (\(1 \le N \le 1000, 1 \le Q \le 2 \cdot 10^5\)).
• \(N\) dòng tiếp theo: Mỗi dòng gồm \(N\) số nguyên biểu diễn bảng số.
• \(Q\) dòng tiếp theo: Mỗi dòng gồm 4 số \(x_1, y_1, x_2, y_2\) (\(1 \le x_1 \le x_2 \le N, 1 \le y_1 \le y_2 \le N\)).

Output

• Với mỗi truy vấn, in ra tổng hình chữ nhật con tương ứng.

Example

4 3
1 2 3 4
5 6 7 8
1 1 1 1
2 2 2 2
1 1 2 2
2 2 3 3
1 1 4 4

14
15
48

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(N \le 100, Q \le 1000\).
• Subtask \(2\) (\(70\%\) số điểm): Không có ràng buộc gì thêm.