닭강정의 전설

진주 가까이에 있는 창원에 사는 아림이는 보선이가 진주 나들이를 온 사실을 알고 오랜만에 만나서 맥주나 마시자고 보선이에게 연락했다. 보선이도 반가운 마음에 알겠다고 즉답했지만, 뒤늦게 한 가지 사실을 떠올렸다. 그 사실은 바로 아림이는 맥주를 아무리 마셔도 취하지 않는 '맥주 한정 주당'이라는 것이었다. '소주 한정 주당' 보선이는 아림이와 맥주를 마시면 술에 진탕 취할 것이 뻔하다는 생각이 들었고, 경상국립대에 대대로 내려오는 닭강정의 전설을 믿어보기로 하였다.

닭강정의 전설은 '경상국립대 후문에서 파는 특별한 닭강정이 있는데, 그 닭강정은 취기를 막아주는 정도가 있다.'라는 전설이다. 이 전설을 믿고 보선이는 경상국립대 후문 쪽에 있는 특별한 닭강정을 파는 가게에 갔는데, 그 가게의 판매 시스템은 보통 닭강정 가게와 다르게 특이했다. 특이한 판매 시스템은 다음과 같다.

• $N × N$ 크기의 격자가 있고, 칸마다 1g의 닭 순살이 있다.
• $i$번째 줄의 $j$번째 칸의 순살은 상수 $k_{i,j}$를 지닌다.
• 구매자는 두 점 $(r_1, c_1)$, $(r_2, c_2)$를 고를 수 있다. 두 점을 고르면 $r_1 ≤ r ≤ r_2$와 $c_1 ≤ c ≤ c_2$를 동시에 만족하는 모든 $(r, c)$ 칸의 순살들을 뭉쳐서 튀긴다.
• 이때, 튀겨진 닭강정의, 취기를 막아주는 정도는 다음과 같이 계산된다.$$\sum_{i={r_1}}^{r_2} \sum_{j={c_1}}^{c_2} \pmatrix{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}}$$

이러한 판매 시스템이 복잡하다 보니, 이 가게에는 구매자가 $(r_1, c_1)$, $(r_2, c_2)$를 고르면 고른 두 점에 따라 튀겨지는 닭강정의, 취기를 막아주는 정도를 자동으로 계산하는 기계가 있다. 그런데 이 기계가 하필 보선이가 방문한 날에 고장이 나버렸다! 그래서 보선이는 옆에 있던 우리한테 $(r_1, c_1)$, $(r_2, c_2)$를 고를 때마다 고른 두 점에 따라 튀겨지는 닭강정의, 취기를 막아주는 정도를 계산해 달라고 부탁했다.

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

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

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

$2+N$번째 줄에는 두 점 $(r_1, c_1)$, $(r_2, c_2)$를 고르는 횟수 $Q$가 주어진다. $(1 ≤ Q ≤ 100\,000)$

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

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

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

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