Cho bảng số gồm ~M~ hàng và ~N~ cột, hàng thứ ~i~ cột thứ ~j~ của bảng số gọi là ô (~i,j~) có giá trị ~a_(i,j)~. Cho 4 số nguyên dương ~x_1,y_1,x_2,y_2~ (~1≤x_1≤x_2≤M;1≤y_1≤y_2≤N~).

Yêu cầu:

Tính tổng các giá trị của các ô nằm trên hình chữ nhật có góc trái trên là ô (~x_1,y_1~) và góc phải dưới là ô (~x_2,y_2~ ).

Input

-Dòng đầu gồm hai số nguyên dương ~M~ và ~N~ (~1≤M,N≤1000~);

-Trong ~M~ dòng tiếp theo, dòng thứ ~i~ gồm ~N~ số nguyên ~a_i1,a_i2,…,a_iN~ (~|a_ij│≤100~);

-Dòng tiếp theo gồm duy nhất một số nguyên dương ~T~- số lượng câu hỏi (T≤10^4 );

-~T~ dòng sau, mỗi dòng gồm 4 số nguyên dương ~x_1,y_1,x_2,y_2~ (~1≤x_1≤x_2≤M;1≤y_1≤y_2≤N~).

Output

In ra ~T~ dòng, mỗi dòng là tổng các giá trị của các ô nằm trên hình chữ nhật có góc trái trên là ô (~x_1,y_1~) và góc phải dưới là ô (~x_2,y_2~ ) tương ứng.

Ví dụ:

input

2 3
1 2 3
2 3 4
2
1 1 2 2
1 2 2 3

output

8

12