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
2019-06-27 14:48:24 mehmetin
Image doesn't show, image link is dead.
2012-12-11 18:40:24 (Tjandra Satria Gunawan)(曾毅昆)
@Ehor Nechiporenko: Thanks for comment to this problem, so I found this 'fun' problem ;-) I'm happy too to become the best solver for now with O(F) complexity and O(M*N) space :-D done in 1,4s with C code.
@Devendra Agarwal: Based on my experiment, constrains for r,i,j: 2i<=r+i<=M and 2j<=r+j<=N so all area will be inside the matrix, and be careful I got SIGSEGV with 1000x1000 array and got AC with 1001x1001 array.
2012-12-11 15:46:44 Ehor Nechiporenko
Today is my happy day. I have resolved this problem))
2012-07-26 14:33:08 devu
@Angel Paredes:Are u sure that r will always be smaller than or equal to i and j.
2012-02-29 02:27:08 Angel Paredes
You can assume the whole funny area will be inside the matrix.
2012-02-28 01:22:10 Brian Curcio
Can we assume the center of the funny area is inside the matrix? Can we assume anything of r?
2012-02-16 18:11:46 :D
I know scanf is slower, I just meant it could be also enough here. See fread and fwrite functions.
2012-02-15 15:17:07 Santiago Palacio
parsing with getchar is faster than scanf, tested in many test cases, neither using fread reading the entire input) and then parsing char by char would do... :\ i dont know any faster input method. How do you buffer the input? thanks in advance for your help.
2012-02-15 07:28:25 :D
I never actually used getchar_unlocked on spoj so I don't know what efficiency boost will it give. Processing char by char could be enough, bu I also use input buffering. You can also try simply with scanf. I don't know exactly how many test cases are there, so I don't know exactly. For linear problems like this one, input reading often takes majority of execution time (even over 90%). Of course, unless cache efficiency is poor, which can also be an issue here.
2012-02-15 05:05:16 Santiago Palacio
The input is i j r? or j i r?, as far as i know, x is in the horizontal line.

@:D what do you mean by fast input? parsing with getchar_unlocked in C wont do? does it needs something faster? becouse an O(r) algorithm (for each case) just wont do...

Last edit: 2012-02-15 05:29:56
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.