e-olymp
Competitions

December 4 - BMTK Programming School, High League

Sum in a matrix

The matrix of integers aij is given, where 1in, 1jm. For given lx, ly, rx, ry find

prb684

Input

The first line contains the size of the matrix - n, m (1n, m1000). Next n lines contains m numbers aij (1aij1000), separated with a space. The line number n + 2 contains number of queries q (1q106). In the next q lines the queries are given lxi, lyi, rxi, ryi (1lxirxin, 1lyiryim).

Output

Print q numbers in separate lines - the answers to the queries.

Time limit 1 seconds
Memory limit 128 MiB
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
Author В.Гольдштейн
Source Зимние сборы в Харькове 2010 День 2