Jujisu

King Jingyeong of the Square Kingdom wants to rule his land more easily, so he plans to bundle many $1 \times 1$ unit districts into one large administrative region called a jujisu (州地數, a count of a village's land). To decide how to bundle them he needs a reference table of how many people live inside a rectangular range.

The king is a very solemn man, so he announces a rectangular range with four numbers and nothing more.

Suppose people live as in the picture above. When the king wants to know how many people live in the rectangular range of Figure 1, he calls out the four integers 1 1 3 2. In the same way Figure 2 is 1 1 1 4 and Figure 3 is 1 1 4 4.

Write a program that builds this reference table for the king.

The first line has the size of the land, $N$ and $M$ ($1 \le N, M \le 1024$).

Each of the next $N$ lines has $M$ integers. The $j$-th number on the $i$-th line is how many people live in the unit district at row $i$, column $j$. At least one person lives in every unit district, and no unit district holds more than 100 people.

The next line has $K$, the number of rectangular ranges the king asks about ($1 \le K \le 100\,000$).

Each of the next $K$ lines has four integers $x_1$, $y_1$, $x_2$, $y_2$ that describe a rectangular range ($1 \le x_1 \le x_2 \le N$, $1 \le y_1 \le y_2 \le M$). The range holds every unit district from row $x_1$ to row $x_2$ and from column $y_1$ to column $y_2$.

Print $K$ lines. On the $i$-th line print the total number of people living inside the $i$-th rectangular range, in the order the ranges are given.