In Pinar Del Río there is a Tabbaco plantation field with rectangular shape, it measures R x C meters ~(1 <= R <= 1000)~ and ~(1 <= C <= 1000)~ such that it can be divided into cells of 1 square meter. Each cell has a seed planted on it, and each seed has an integer value ~V (|V| <= 10)~ associated to it, which means the height at which the plant of tabacco can grow out of it. In this field is common to find that some seeds are not smart enough to know that the plant that comes out of it has to grow up towards the sun, and sadly they grow underground, that's the reason why some seeds has negative values (yes, it can happen, don't forget those seeds are from Pinar Del Río).

Don Alejandro the owner of the plantation wants to examine some parts of the field, there for he will be asking you ~Q (1 <= Q <= 10^5)~ queries. In each query he will ask for the sum of the heights of all plants that grow towards the sun in a sub-rectangle of the field. The upper left cell of the field is [1, 1].

Especificación de entrada

The first line contains three space separated integers ~R (1 <= R <= 1000)~, ~C (1 <= C <= 1000)~, and ~Q (1 <= Q <= 10^5)~. The next R lines describe the field, each line contains C space separated integers ~V1, V2, ..Vc (|Vi| <= 10)~ representing the value associated to a seed.

The next Q lines contain the description of a single query, consisting of four integers x1, y1, x2, y2 where [x1, y1] is the sub-rectangle's upper left corner and [x2, y2] is the sub-rectangle's lower right corner. It is guaranteed that each pair represent a valid cell inside the field.

Especificación de salida

For each query print a line containing a single integer the sum of the heights of all plants that grow towards the sun in the queried sub-rectangle.

Ejemplo de entrada

3 3 3
3 1 -3
2 5 7
-1 2 -5
1 1 3 3
1 2 2 3
3 2 3 3

Ejemplo de salida

20
13
2