En Pinar del Río hay una plantación de Tabaco con forma rectangular que mide R x C metros, ~(1 \leq R \leq 1000)~ and ~(1 \leq C \leq 1000)~ de modo que puede dividirse en celdas de un metro cuadrado. Cada celda tiene una semilla sembrada y cada semilla tiene un valor entero ~V (|V| \leq 10)~ asociado, que representa la altura a la cual la planta de tabaco puede crecer fuera de la semilla. En este campo es común ver como algunas semillas no son tan inteligentes como para saber que la planta que crecerá de la semilla, debe crecer hacia el sol. De este modo las semillas crecen en dirección subterránea y como resultado tienen valores negativos.

Don Alejandro es el dueño de la plantación y quiere examinar algunas partes del campo. Para ello te hará una serie de ~Q (1 \leq Q \leq 10^5)~ consultas. En cada consulta él desea conocer la suma de las alturas de todas las plantas que crecen hacia el sol en un subrectángulo del campo. La esquina superior izquierda del campo tiene coordenadas [1, 1].

Entrada

La primera línea contiene tres enteros ~R (1 \leq R \leq 1000)~, ~C (1 \leq C \leq 1000)~, and ~Q (1 \leq Q \leq 10^5)~ separados por un espacio. Las siguientes R líneas describen la información del campo. Cada línea contiene C enteros separados por espacios ~V_1, V_2, ..., V_c (|V_i| \leq 10)~ que representan el valor asociado a una semilla. Las siguientes ~Q~ líneas contienen la descripción de una consulta. Esta consiste de cuatro enteros ~x_1~, ~y_1~, ~x_2~, ~y_2~ donde ~[x_1, y_1]~ es la esquina superior izquierda del subrectángulo ~y [x_2, y_2]~ es la esquina inferior derecha. Se garantiza que cada par representa una celda válida dentro del campo.

Salida

Para cada consulta imprima una línea con la suma de las alturas de todas las plantas que crecen hacia el sol en el subrectángulo consultado.

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