Cho bảng chữ nhật ~m~ x ~n~ (các hàng được đánh số từ ~1~ tới ~m~ từ trên xuống dưới, các cột được đánh số từ ~1~ tới ~n~ từ trái sang phải). Mỗi ô ở hàng ~i~ cột ~j~ có chứa một số nguyên ~a_{ij}~.

Tổng chéo của một hình vuông có ô ở đỉnh trái trên ~[x,y]~ và cạnh độ dài ~k~ được tính bằng tổng của tất cả những số nằm trên 2 đường chéo chính.

Ví dụ, với bảng ~5~ x ~6~, hình vuông có đỉnh trái trên ~[2, 2]~ với độ dài cạnh là ~3~ có tổng chéo bao gồm các ô sau:

Yêu cầu

Cho bảng số ~m~ x ~n~ và ~q~ truy vấn. Mỗi truy vấn cho 3 số ~x~, ~y~, ~k~, tính tổng chéo của hình vuông có đỉnh trái trên ở toạ độ ~[x, y]~ và cạnh độ dài ~k~.

Input

• Dòng đầu tiên chứa 3 số nguyên dương ~m~, ~n~, ~q~ ~(m,n≤2000, q≤10^6)~ cách nhau một dấu cách.
• ~m~ dòng sau, mỗi dòng chứa ~n~ số nguyên ~a_{ij}~ có giá trị tuyệt đối không vượt quá ~10^9~ cách nhau một dấu cách.
• ~q~ dòng tiếp theo, mỗi dòng là một truy vấn chứa 3 số nguyên dương ~x~, ~y~, ~k~ ~(x≤m, y≤n)~, ~k~ luôn đảm bảo hình vuông nằm trong bảng số.

Output

Gồm ~q~ dòng, mỗi dòng chứa một số nguyên dương là tổng chéo tương ứng.

Sample Input

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

Sample Output

3
1
5

Subtask

• Có 50% số test ứng với 50% số điểm có ~q≤2000~;
• 50% số test còn lại tương ứng với 50% số điểm không có giới hạn gì thêm.