MATSUM - Matrix Summation

no tags 

A N × N matrix is filled with numbers. BuggyD is analyzing the matrix, and he wants the sum of certain submatrices every now and then, so he wants a system where he can get his results from a query. Also, the matrix is dynamic, and the value of any cell can be changed with a command in such a system.

Assume that initially, all the cells of the matrix are filled with 0. Design such a system for BuggyD. Read the input format for further details.

Input

The first line of the input contains an integer t, the number of test cases. t test cases follow.

The first line of each test case contains a single integer N (1 <= N <= 1024), denoting the size of the matrix.

A list of commands follows, which will be in one of the following three formats (quotes are for clarity):

  1. "SET x y num" - Set the value at cell (x, y) to num (0 <= x, y < N).
  2. "SUM x1 y1 x2 y2" - Find and print the sum of the values in the rectangle from (x1, y1) to (x2, y2), inclusive. You may assume that x1 <= x2 and y1 <= y2, and that the result will fit in a signed 32-bit integer.
  3. "END" - Indicates the end of the test case.

Output

For each test case, output one line for the answer to each "SUM" command. Print a blank line after each test case.

Example

Input:
1
4
SET 0 0 1
SUM 0 0 3 3
SET 2 2 12
SUM 2 2 2 2
SUM 2 2 3 3
SUM 0 0 2 2
END

Output:
1
12
12
13
Warning: large Input/Output data, be careful with certain languages

hide comments
Ðộc cô cầu bại: 2011-05-14 15:16:18

@Avinash: Because you can't sum one square twice :))

Avinash: 2011-03-25 04:04:33

why second line of output is not 24??
set 2 2 12
sum 2 2 2 2 it means sum (12)+(12)-->24

Last edit: 2011-03-25 04:09:14
biQar: 2010-10-05 17:27:36

@ Hy Trường Sơn & paddyHOD - u can use 2D bit for this problem !! ;)

paddyHOD: 2010-09-27 15:48:57

my algo is very slow,some please tell me which data structure should i take.

Last edit: 2010-09-27 15:49:22
Hy Trường Sơn: 2009-06-13 09:34:40

my algorithm is very slow. I use segment tree

Brian Bi: 2009-04-26 23:51:03

There is a blank line, but you can't see it because it's at the end. In case it wasn't clear, note that there is actually only one case shown in the sample (so there are no blank lines "between").

Also, I got AC with the assumption that num fits into an int [which is a signed 32-bit integer in C/C++]

Last edit: 2009-04-26 23:53:13
Omar ElAzazy: 2009-04-26 18:26:28

"the result will fit in a signed 32-bit integer." does that make num( number to put at place (x,y) ) never exceed signed 32-bit integer limits ??

Everything fits in int.

Last edit: 2011-03-06 08:55:35

Added by:Matthew Reeder
Date:2006-10-29
Time limit:1.029s
Source limit:30000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:Al-Khawarizm 2006