Hôm nay Anh Mạnh iu dấu sẽ chỉ các bé về mảng cộng dồn nha, Anh Mạnh có một mảng hai chiều ~A~ có ~N \times M~ số nguyên và hãy trả lời anh Mạnh ~Q~ câu hỏi mà anh Mạnh đã đề ra là đố bạn tổng các số trong hình chữ nhật từ phần tử thứ ~(x_1,y_1)~ tới phần tử thứ ~(x_2,y_2)~ là bao nhiêu

Input

• Hai số nguyên là ~N, M(1 \leq N, M \leq 10^3)~, đại diện cho số hàng và số cột của mảng ~A~
• Dòng tiếp theo gồm ~N~ hàng và mỗi hàng có ~M~ phần tử ~a_{i,j}( 1 \leq i \leq N, 1 \leq j \leq M, 1 \leq a_{i,j} \leq 10^9 )~ của mảng ~A~.
• Dòng tiếp theo có duy nhất 1 số nguyên ~Q~, đại diên cho số truy vấn
• Và ~Q~ dòng tiếp theo với mỗi dòng gồm 4 số nguyên ~x_1, y_1, x_2, y_2( 1 \leq x_1 \leq x_2 \leq N, 1 \leq y_1 \leq y_2 \leq M )~, đại diện cho truy vấn hình chữ nhật từ phần tử thứ ~(x_1,y_1)~ tới phần tử thứ ~(x_2,y_2)~

Output

• Mỗi dòng in ra câu trả lời của mỗi truy vấn

Sample Input

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

Sample Output

18