Final Fantasy XIV(ff14) is a 3D massively multiplayer online role-playing game(MMORPG) developed by square Enix, a Japanese game developer. It is the fourteenth game work in the Final Fantasy series. Since it was published, ff14 has attracted many players with its grand stories, beautiful graphics ,fine-sounding soundtrack and rich game content. 

Rover is a crazy ff14 player. Now, he decides to challenge the most difficult duty of this game: the Unending Coil of Bahamut (Ultimate) with his favorite role: Black Mage. The field of this duty is a grid with n rows and m columns. The grid point (i, j) in row i and column j contains a_i,j monsters. Rover is a player who attaches great importance to efficiency, so he decides to use his strongest Area of effect action: Foul, which could attack many monsters at a time.

The effect of this action is as follows: Each time Rover will choose a grid point (r, c) (representing the grid point in row r and column c), and then choose a range d. Monsters within grid point he chose d distance will be attacked (Note: the distance here refers to Manhattan distance. In other words, for each grid point (i, j), if it satisfies , all monsters located in grid point (i, j) will be attacked.

Rover is ready to use this action q times. Now he wants to know how many monsters will be attacked every time after he uses this action. Because Rover forgot to wear his best equipment, so monsters will not be killed after being attacked.

输入描述:

The first line contains three single integers  — the number of rows, the number of columns in the grid, and the number of times Rover use the action.
The following n lines describe the grid. The i-th of the n lines contains m integers  — the number of monsters in the grid points.
Then, the following q lines describe the action. The i-th of the q lines contains three integers , represents Rover chooses the grid point in row ri and column ci, and attack all the monsters within the grid point di distance.

输出描述:

Print q lines. Each line contains an integer. The i-th line represents the number of monsters attacked by Rover in the i-th action.

4 4 2
8 6 5 6
6 4 8 4
4 4 3 6
1 1 8 9
1 4 2
2 1 1

35
22

备注:

Note: The input may be very large, you can use this way to read the test data：

inline int read()
{
    int X=0,Y=1;char C=getchar();
    while (C<'0'||C>'9') {if (C=='-') Y=-1;C=getchar();}
    while (C>='0'&&C<='9') X=X*10+C-'0',C=getchar();
    return X*Y;
}