Tổng bảng con


Submit solution

Points: 1
Time limit: 1.0s
Memory limit: 1G

Problem type

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

There are no comments at the moment.