닭강정의 전설

아림이는 창원에 살며, 맥주를 아무리 마셔도 취하지 않는 '맥주 한정 주당'이다. 보선이는 '소주 한정 주당'이라서, 아림이와 맥주를 마시면 술에 크게 취할 것이 뻔하다고 생각했다. 그래서 경상국립대 후문에 대대로 내려오는 닭강정의 전설을 믿어 보기로 했다.

전설에 따르면 경상국립대 후문에서 파는 특별한 닭강정에는 취기를 막아 주는 정도가 있다. 보선이는 그 가게를 찾아갔다. 가게의 판매 방식은 보통 닭강정 가게와 달랐다.

판매 방식은 다음과 같다.

• $N \times N$ 크기의 격자가 있고, 각 칸에는 1g의 닭 순살이 있다.
• $i$번째 줄의 $j$번째 칸에 있는 순살은 상수 $k_{i,j}$를 지닌다.
• 구매자는 두 점 $(r_1, c_1)$, $(r_2, c_2)$를 고를 수 있다. 두 점을 고르면 $r_1 \le r \le r_2$이고 $c_1 \le c \le c_2$를 동시에 만족하는 모든 칸 $(r, c)$의 순살을 뭉쳐서 튀긴다.
• 튀긴 닭강정의 취기를 막아 주는 정도는 다음 식으로 계산한다.

$\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}$

판매 시스템이 복잡해서, 가게에는 두 점을 고르면 취기 방지 정도를 자동으로 계산하는 기계가 있다. 그런데 보선이가 방문한 날 기계가 고장 났다. 보선이는 옆에 있던 우리에게 두 점을 고를 때마다 취기를 막아 주는 정도를 계산해 달라고 부탁했다.

이제 보선이의 부탁을 들어주자.

첫 번째 줄에 격자의 크기 $N$이 주어진다. ($5 \le N \le 5\,000$)

두 번째 줄부터 $N$개의 줄에 걸쳐 $i$번째 줄의 $j$번째 칸에 있는 순살의 상수 $k_{i,j}$가 공백으로 구분되어 $N$개씩 주어진다. ($1 \le k_{i,j} \le 10$)

$N+2$번째 줄에는 두 점을 고르는 횟수 $Q$가 주어진다. ($1 \le Q \le 100\,000$)

$N+3$번째 줄부터 $Q$개의 줄에 걸쳐 $r_1$, $c_1$, $r_2$, $c_2$가 공백으로 구분되어 주어진다. ($1 \le r_1, c_1, r_2, c_2 \le N$; $r_1 + 2 \le r_2$; $c_1 + 2 \le c_2$)

입력으로 주어지는 모든 수는 정수이다.

$Q$개의 줄에 걸쳐 각 질의의 $r_1$, $c_1$, $r_2$, $c_2$에 따라 튀겨지는 닭강정의 취기를 막아 주는 정도를 한 줄에 하나씩 출력한다.

Python 3 사용자는 PyPy3로 제출할 것을 권장한다.