Descripción

"¡Ahhhhh! ¿qué rápido se acaban las vacaciones verdad?... Pero no estés triste Matojo, regresando a la uni vas a poder ver a Patricia, esa muchachita que te tiene loco".

Matojo fingió que no le importaba, como si el regreso a clases fuera ir a ver el tiempo pasar y no ese momento exacto en el que la vida te vuelve a poner enfrente lo que más extrañabas. Pero la verdad es que sí le importaba mucho. Porque Patricia no era cualquier persona: era la razón por la que Matojo, de repente, quería "ponerse al hilo", "ser el más inteligente", "no llegar tarde" y "ponerse perfume", ya saben como se pone uno cuando se enamora.

El problema fue que al volver de vacaciones de invierno, el caos cayó sobre club programación como cae enero: sin pedir permiso. El salón del club quedó lleno de cajas con material para arrancar el semestre (hojas, plumones, stickers, gafetes, pinnes por doquier, etc.). Para organizar todo, dibujaron un mapa del cuarto como una cuadrícula de \(N\) filas por \(M\) columnas, y en cada casilla anotaron cuántos objetos había ahí.

Y entonces Patricia soltó de la nada:

Matojo, necesito que me digas rápido cuántos materiales hay en ese bloque de cajas.

Cada pregunta de Patricia describe un rectángulo del mapa por su esquina superior izquierda \((R_1, C_1)\) y su esquina inferior derecha \((R_2, C_2)\).

Matojo quiere responder sin titubear (por eficiencia… y ya saben, ¡por Patricia!). Se le ocurrió utilizar un programita que tenía guardado de sus estudios de ICPC para así poder contestar las \(Q\) preguntas que le hiciera su amada Patricia con el valor exacto de materiales que hay en el bloque de cajas(rectángulo).

Entrada

La entrada tiene el siguiente formato:

• En la primera línea se leen dos enteros \(N\) y \(M\) \((1 \leq N, M \leq 2000)\)
• Siguen \(N\) líneas, cada una con \(M\) enteros \(A_{ij}\) \((-10^4 \leq A[i][j] \leq 10^4)\), el mapa del salón del club.
• Luego se lee un entero \(Q\) \((1 \leq Q \leq 2*10^5)\), el número de preguntas de Patricia.
• Finalmente, siguen \(Q\) líneas con cuatro enteros \(R1\), \(C1\), \(R2\), \(C2\) cumpliendo \((0 \leq R_1 \leq R_2 \le N)\) y \((0 \leq C_1 \leq C_2 \le M)\).

Salida

Imprime \(Q\) líneas. En la i-ésima línea, imprime un entero: la suma total de materiales en el bloque de cajas \([(R_1, C_1), (R_2, C_2)]\).

Ejemplo

Entrada

3 4
1 2 3 4
5 6 7 8
9 10 11 12
3
0 0 1 1
1 2 2 3
0 1 2 2

Salida

14
38
39