2D Array Range Sum

You are given an N by M array of integers. For each query, compute the sum of all numbers in the rectangular region whose top-left position is (i, j) and bottom-right position is (x, y).

The position (i, j) means row i and column j.

The first line contains the array dimensions N and M. (1 <= N, M <= 300)

Each of the next N lines contains M integers, describing one row of the array. Every number in the array has absolute value at most 10,000.

The next line contains K, the number of rectangular-sum queries. (1 <= K <= 10,000)

Each of the next K lines contains four integers i, j, x, and y. This asks for the sum from (i, j) to (x, y), and it always satisfies 1 <= i <= x <= N and 1 <= j <= y <= M.

For each query, in the order given, print the sum of the numbers in the requested rectangle on its own line. Each sum is at most 2^31 - 1.