Bạn được cho một ma trận (bảng) A kích thước M x N. Sau đó, bạn sẽ nhận được Q truy vấn. Mỗi truy vấn gồm 4 số nguyên x1, y1, x2, y2, đại diện cho tọa độ góc trên trái (x1, y1) và góc dưới phải (x2, y2) của một hình chữ nhật con.

Với mỗi truy vấn, nhiệm vụ của bạn là tính và in ra tổng của tất cả các ô A[i][j] nằm trong hình chữ nhật con đó (với x1 <= i <= x2 và y1 <= j <= y2).

Gợi ý: Nếu tính tổng bằng 2 vòng for lồng nhau cho mỗi truy vấn, thuật toán sẽ có độ phức tạp O(Q.M.N) và chắc chắn sẽ bị "Chạy quá thời gian".

Thay vào đó, hãy sử dụng Mảng Cộng Dồn 2 Chiều.

Xây dựng (O(M.N)): Tạo một ma trận P kích thước (M+1) x (N+1). P[i][j] = Tổng của tất cả các ô trong hình chữ nhật từ (1, 1) đến (i, j). Công thức xây dựng P: P[i][j] = A[i][j] + P[i-1][j] + P[i][j-1] - P[i-1][j-1]

Truy vấn (O(1)): Với mỗi truy vấn (x1, y1, x2, y2), tổng của hình chữ nhật con được tính bằng công thức (dựa trên nguyên lý bù trừ): Tong = P[x2][y2] - P[x1-1][y2] - P[x2][y1-1] + P[x1-1][y1-1]

Input:

Dòng đầu tiên chứa 2 số nguyên M, N.

M dòng tiếp theo, mỗi dòng chứa N số nguyên A[i][j], là các giá trị của ma trận.

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

Q dòng tiếp theo, mỗi dòng chứa 4 số nguyên x1, y1, x2, y2.

Output:

In ra Q dòng, mỗi dòng là kết quả (tổng) cho một truy vấn tương ứng.

Ràng buộc:

1 <= M, N <= 1000

1 <= Q <= 100000

-1000 <= A[i][j] <= 1000

1 <= x1 <= x2 <= M

1 <= y1 <= y2 <= N

(Tổng của một truy vấn có thể lớn, nên dùng long long để lưu mảng P và kết quả)

Ví dụ 1:

Input:

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

Output:

14
20