You are given an ~N \times M~ grid of integers, with rows numbered from ~1~ to ~N~, and columns numbered from ~1~ to ~M~. You are also given ~Q~ queries. Each query consists of ~4~ integers: ~r_1~, ~c_1~, ~r_2~, and ~c_2~, where ~(r_1,c_1)~ represents top-left most cell of a rectangle, and ~(r_2,c_2)~ represents the bottom-right most cell of the rectangle.

Input Specification

The first line of input contains ~N~, ~M~, and ~Q~.

The next ~N~ lines each contain ~M~ integers, where the ~i^{th}~ line contains the integers in the ~i^{th}~ row of the grid. All integers in the grid are positive and less than or equal to ~1000~.

The next ~Q~ lines each contain ~4~ integers: ~r_1~, ~c_1~, ~r_2~, and ~c_2~.

Output Specification

Output ~Q~ lines, where the ~i^{th}~ line contains the sum of numbers contained within the rectangle described by the ~i^{th}~ query.

Constraints

~2 \leq N, M \leq 1000~

~1 \leq Q \leq 10^6~

Sample Input

5 4 3
2 3 5 8
6 4 8 6
1 4 2 7
4 7 6 5
1 9 1 3
1 1 2 3
2 4 5 4
3 1 5 3

Sample Output

28
21
35