Responsive image

问题 1536 --Large Number of Sub-Matrixes

1536: Large Number of Sub-Matrixes

时间限制: 2 Sec  内存限制: 128 MB
提交: 2  解决: 1
[提交][状态][讨论版][命题人:]

题目描述

Given an M*N matrix A, whose entries Ai,j are integer numbers ( 1 <= i <= M, 1 <= j <= N ), please sum all elements of a given sub-matrix. 

输入描述

The first line of the input contains two integers M and N indicating the number of rows and columns of a matrix. The following M lines have N integers each. The next line contains a single integer C indicating the number of sub-matrixes. Each of the following C lines contains four integers x1, y1, x2 and y2 (with x1 ≤ x2 and y1 ≤ y2) indicating the top left and bottom right of the sub-matrix.

You may assume 2 ≤ M ≤ 1000 , 2 ≤ N ≤ 1000 and C ≤ 1000000.

输出描述

Your output must contain C lines with one integer on each line. Each line contains the sum of all elements of the given sub-matrix.

样例输入

4 4 
1 2 3 4
4 5 6 7
8 9 10 11
12 13 14 15
2
1 1 2 2
2 1 2 3

样例输出

12
15

来源

zj 

[提交][状态]
ACM算法攻关部