Tudor lại đang ngồi trong giờ Tin học và cắm cúi gõ laptop, rõ ràng là cậu ấy chẳng hề chú ý đến bài giảng về kỹ thuật mảng cộng dồn hai chiều. Thấy vậy, giáo viên quyết định gọi Tudor lên bảng làm bài tập. Thầy cho Tudor một bàn cờ kích thước ~N \times N~, mỗi ô ghi một số nguyên. Bàn cờ được tô hai màu xen kẽ: ô ~(1, 1)~ ở góc trên bên trái là ô trắng, ô ~(i, j)~ là ô trắng khi ~i + j~ chẵn và là ô đen khi ~i + j~ lẻ. Thầy đưa ra liên tiếp ~q~ câu hỏi, mỗi câu hỏi yêu cầu tính giá trị tuyệt đối của hiệu giữa tổng các ô trắng và tổng các ô đen nằm trong một vùng hình chữ nhật xác định. Đối với bạn thì bài toán này thật đơn giản, nhưng với Tudor thì không hề dễ dàng chút nào. Bạn hãy giúp Tudor một tay nhé!

Input Specification

Dòng đầu tiên chứa số nguyên ~N~ (~1 \le N \le 500~).

~N~ dòng tiếp theo, mỗi dòng chứa ~N~ số nguyên ~a_{i, 1}, a_{i, 2}, \dots, a_{i, N}~ (~0 \le a_{i, j} \le 100~) biểu thị các giá trị trên bàn cờ.

Dòng tiếp theo chứa số nguyên ~q~ (~1 \le q \le 10^4~) là số lượng truy vấn cần trả lời.

~q~ dòng sau, mỗi dòng chứa bốn số nguyên ~i_1, j_1, i_2, j_2~ (~1 \le i_1 \le i_2 \le N~ và ~1 \le j_1 \le j_2 \le N~) tương ứng với tọa độ đỉnh trên bên trái ~(i_1, j_1)~ và đỉnh dưới bên phải ~(i_2, j_2)~ của vùng hình chữ nhật cần khảo sát.

Output Specification

In ra ~q~ dòng:

• Mỗi dòng ghi một số nguyên duy nhất là kết quả giá trị tuyệt đối của hiệu giữa tổng các ô trắng và tổng các ô đen tương ứng với truy vấn đó.

Sample Input

3
2 5 1
4 3 6
1 2 8
2
1 1 2 3
2 2 3 3

Sample Output

9
3

(Ghi chú:

• Truy vấn 1 xét hình chữ nhật ~[(1, 1) \to (2, 3)]~:
• Các ô trắng (~i + j~ chẵn): ~(1, 1) = 2~, ~(1, 3) = 1~, ~(2, 2) = 3 \implies \text{Tổng trắng} = 2 + 1 + 3 = 6~.
• Các ô đen (~i + j~ lẻ): ~(1, 2) = 5~, ~(2, 1) = 4~, ~(2, 3) = 6 \implies \text{Tổng đen} = 5 + 4 + 6 = 15~.

• Kết quả: ~|6 - 15| = 9~.

• Truy vấn 2 xét hình chữ nhật ~[(2, 2) \to (3, 3)]~:

• Các ô trắng: ~(2, 2) = 3~, ~(3, 3) = 8 \implies \text{Tổng trắng} = 3 + 8 = 11~.
• Các ô đen: ~(2, 3) = 6~, ~(3, 2) = 2 \implies \text{Tổng đen} = 6 + 2 = 8~.
• Kết quả: ~|11 - 8| = 3~).