There is an M x N matrix of integer numbers.  Both the rows and columns of the matrix are numbered starting at 0 and ending at M-1 and N-1 respectively.

A funny area is defined by three integers i, j, and r, and it is composed for those cells [x, y] such that |i-x| + |j-y| <= r. As you might have probably guessed [i, j] is the center and r is the radius of the funny area.

In this problem we are interested in finding the sum of every cell inside some given funny areas.

Input

The first line contains two integers 1 <= M, N <= 1000 representing the rows and columns of the matrix.

Each of the following M lines contains N integers separated by single spaces. These numbers are non-negative and not greater than 1,000,000,000

The next line contains a number F (1 <= F <= 100,000) which is the number of funny areas.

Each of the following F lines contains three integers i, j, and r representing the center and the radius of a funny area.

Output

F lines: for each funny area print a single number -- the sum of all the cells inside of it.

Example

Input
5 5
1 2 3 4 5
5 4 3 2 1
1 1 1 1 1
2 3 4 3 0
7 8 9 6 5
3
1 0 0
2 2 2
3 1 1

Output
5
36
18