Tổng bảng con
Cho một bảng chữ nhật $N$ hàng, $M$ cột. Các hàng được đánh số từ 1 đến $N$ từ trên xuống dưới. Các cột được đánh số từ 1 đến $M$ từ trái sang phải. Ô ở hàng $i$, cột $j$ là ô $a_{i,j}$.
Cho $Q$ truy vấn, mỗi truy vấn hãy in ra tổng các phần tử của bảng con có ô trái trên là $(x,y)$ và phải dưới là $(p,q)$.
Dữ liệu
- Dòng đầu tiên chứa ba số nguyên $N, M, Q \ (0<N,M\le10^3;0<Q\le10^5)$;
- $N$ dòng tiếp theo, mỗi dòng chứa $M$ số nguyên $a_{i,j} \ (1 \le a_{i,j} \le 10^9)$;
- $Q$ dòng tiếp theo, mỗi dòng chứa bốn số nguyên $x,y,p,q \ (1 \le x \le p \le N; 1 \le y \le q \le M)$.
Kết quả
- In ra trên $Q$ dòng, mỗi dòng là kết quả cho truy vấn tương ứng.
Ví dụ
Ví dụ 1
input
2 3 2
1 2 3
4 5 7
1 1 2 2
1 2 2 3
output
12
17
Comments