FUNAREA - Funny Areas

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


Added by:Angel Paredes
Date:2012-02-13
Time limit:0.100s-1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Copa Lenin 2012 - Level 2

hide comments
2012-02-14 21:29:17 :D
Thanks for the correction. I think it will 'fly' now :) Still, fast input is recommended.
2012-02-14 21:12:26 Angel Paredes
You're right. I completely forgot to set the time to 2 sec for some test cases. Fixed already.

Last edit: 2012-02-13 15:00:22
2012-02-14 21:12:26 :D
Time limit seem very strict here. For 1000x1000 matrix and 10^5 queries it will be very hard to fit 1s, even with fast input. If this limit wasn't verified with running a sample solution on SPOJ, please make it higher.

Last edit: 2012-02-13 14:20:33
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.