Cho ma trận \(A\) kích thước \(N \times M\). Trả lời Q truy vấn tính tổng hình chữ nhật con từ \((x_1, y_1)\) đến \((x_2, y_2)\).

Định dạng đầu vào

• Dòng 1: \(N, M, Q\) (\(1 \le N, M \le 1000, 1 \le Q \le 10^5\)).
• \(N\) dòng tiếp theo: mỗi dòng gồm M số nguyên biểu thị ma trận \(A\).
• \(Q\) dòng tiếp theo: mỗi dòng gồm \(x_1, y_1, x_2, y_2\).

Định dạng đầu ra

• In ra kết quả của từng truy vấn trên một dòng.

Ví dụ

Input:

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

Output:

12

Giải thích: Tổng vùng chữ nhật con là \(1 + 2 + 4 + 5 = 12\).

Ràng buộc & Subtasks