Problems
Sum in a matrix
Sum in a matrix
The matrix of integers aij
is given, where 1 ≤ i ≤ n, 1 ≤ j ≤ m. For given lx
, ly
, rx
, ry
find
Input
The first line contains the size of the matrix - n, m (1 ≤ n, m ≤ 1000). Next n lines contains m numbers aij
(1 ≤ aij
≤ 1000), separated with a space. The line number n + 2 contains number of queries q (1 ≤ q ≤ 106
). In the next q lines the queries are given lxi
, lyi
, rxi
, ryi
(1 ≤ lxi
≤ rxi
≤ n, 1 ≤ lyi
≤ ryi
≤ m).
Output
Print q numbers in separate lines - the answers to the queries.
Input example #1
3 5 1 2 3 4 5 5 4 3 2 1 2 3 1 5 4 5 1 1 3 3 2 2 3 4 2 3 3 5 3 2 3 4 1 4 2 5
Output example #1
24 18 16 9 12