Cho một bàn cờ vua kích thước ~n * n~ , trên mỗi ô của bàn cờ có ghi một con số. Biết ô trên trái của bàn cờ vua là ô trắng (các ô của bàn cờ vua có dạng xen kẽ trắng đen). Các cột được đánh số từ ~1~ đến ~n~ từ trái sang phải, các hàng được đánh số từ ~1~ đến ~n~ từ trên xuống dưới. Ô ở hàng ~i~, cột ~j~ của bàn cờ được ký hiệu là ô (~i, j~).

binminh01 đưa ra những câu đố cho hoangduong như sau: binminh01 sẽ cho hoangduong biết các vùng hình chữ nhật trên bàn cờ, nhiệm vụ của hoangduong là phải tính giá trị tuyệt đối của độ chênh lệch giữa tổng giá trị các ô trắng và tổng giá trị các ô đen trên vùng hình chữ nhật đó. Bạn hãy lập trình giúp hoangduong trả lời các câu đố của binminh01 nhé.

INPUT

Dòng đầu chứa số nguyên dương ~n~ (~1 \le n \le 500~)

~n~ dòng tiếp theo, dòng thứ ~i~ chứa ~n~ số nguyên dương ~a_{i1}, a_{i2}, ..., a_{in}~ là các số ghi trên hàng ~i~ của bàn cờ (từ trái sang phải), mỗi số cách nhau một dấu cách (~0 \le a_{ij} \le 100~)

Dòng tiếp theo ghi số nguyên dương ~q~ là số câu hỏi (~1 \le q \le 10000~)

~q~ dòng tiếp theo, mỗi dòng chứa bốn số nguyên dương ~r_1, c_1, r_2, c_2~ là tọa độ hai đỉnh trên trái và dưới phải của một câu hỏi, mỗi số cách nhau một dấu cách (~1 \le r_1 \le r_2 \le n~, ~1 \le c_1 \le c_2 \le n~).

OUTPUT

Gồm ~q~ dòng, mỗi dòng chứa một số nguyên không âm là các câu trả lời cho ~q~ câu hỏi (theo đúng thứ tự câu hỏi).

SAMPLE INPUT

3
1 3 5 
2 4 6 
0 10 5 
2 
1 1 2 2 
1 2 3 3

SAMPLE OUTPUT

0
5