Submatrix Sum Query

Given a 2-dimensional array ARR with 'N' rows and 'M' columns, and a set of queries in a 2-dimensional array Queries of size 'K', each query contains four integers that denote the top-left and bottom-right indices of a submatrix. Your task is to compute the sum of the elements within the specified submatrix for each query.

Input:

The first line contains an integer, 'T', representing the number of test cases.

For each test case, the first line consists of three integers, 'N', 'M', and 'K', denoting the number of rows, columns in 'ARR', and the number of queries respectively.

The next 'N' lines each contain 'M' integers representing the elements of the array 'ARR'.

The following 'K' lines each contain four integers corresponding to a query from the array 'Queries'.

Output:

For each test case, output 'K' integers, each representing the sum of elements within the submatrix for the respective query.

Each test case result should be printed on a new line.

Example:

Input:
1
3 3 1
1 2 3
3 4 1
2 1 2
0 0 1 2

Output:
14

Constraints:

• 1 ≤ N ≤ 10^3
• 1 ≤ M ≤ 10^3
• 1 ≤ K ≤ 10^3
• 1 ≤ ARR[i][j] ≤ 10^6
• 0 ≤ Queries[i][0], Queries[i][2] < N
• 0 ≤ Queries[i][1], Queries[i][3] < M

Note:

The origin (0, 0) refers to the top-left corner of the matrix, and indices in queries are inclusive.