The Legend of Dakgangjeong

Arim lives in Changwon and is a 'beer-only drinker', so beer never makes Arim drunk. Boseon is a 'soju-only drinker' and is sure that drinking beer with Arim would leave Boseon completely drunk. So Boseon decided to trust the legend of the chicken near the Gyeongsang National University back gate.

According to the legend, a special fried chicken sold near the back gate of Gyeongsang National University has a certain level of intoxication-blocking power. Boseon went to that shop. Its sales system is unlike that of an ordinary chicken shop.

The system works as follows.

• There is an $N \times N$ grid, and each cell holds 1 g of boneless chicken.
• The chicken in row $i$, column $j$ has a constant $k_{i,j}$.
• A buyer picks two points $(r_1, c_1)$ and $(r_2, c_2)$. After the two points are chosen, all chicken in every cell $(r, c)$ with $r_1 \le r \le r_2$ and $c_1 \le c \le c_2$ is packed together and fried.
• The intoxication-blocking level of the fried chicken is computed as follows.

$\sum_{i=r_1}^{r_2} \sum_{j=c_1}^{c_2} k_{i,j} \times \begin{cases} 1 & \text{if } r_1 < i < r_2 \text{ and } c_1 < j < c_2 \\ -1 & \text{otherwise} \end{cases}$

The machine that calculates this for each pair of points broke down on the day Boseon visited. Boseon asked the people nearby to compute the level for every pair of points chosen.

Let's help Boseon.

The first line contains the grid size $N$. ($5 \le N \le 5\,000$)

From the second line onward, the next $N$ lines each contain $N$ space-separated values, where the $j$-th value on the $i$-th line is the constant $k_{i,j}$. ($1 \le k_{i,j} \le 10$)

The line $N+2$ contains the number of queries $Q$. ($1 \le Q \le 100\,000$)

From line $N+3$ onward, the next $Q$ lines each contain $r_1$, $c_1$, $r_2$, $c_2$, separated by spaces. ($1 \le r_1, c_1, r_2, c_2 \le N$; $r_1 + 2 \le r_2$; $c_1 + 2 \le c_2$)

All numbers in the input are integers.

For each of the $Q$ queries, print on its own line the intoxication-blocking level of the fried chicken chosen by $r_1$, $c_1$, $r_2$, $c_2$.

Python 3 users are recommended to submit with PyPy3.