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
Leonardo de Sá Alt: 2012-04-09 21:47:25

Using BIT 2D and getting TLE..

accepted =p
cin -> scanf
cout -> printf
sync_with_stdio didnt make it

Last edit: 2012-04-10 03:16:46
Ihtisham: 2012-02-14 00:03:55

Why am i getting runtime error(SIGSEGV) my code runs fine on ideone.com?

flareneos: 2012-01-12 17:51:51

Guys, I used 2D BIT and I still get TLE. Anyone has an idea why ?

bristy: 2012-01-11 21:04:46

@admin:
please check my submission. I cant see problem in my code. ID:6337875;
I submit same code on "poj.com" got AC, here its giving me WA.
thanks in advance.....

Last edit: 2012-01-11 21:06:22
Krzysztof Lewko: 2011-06-17 17:56:03

@aayush yes

aayush: 2011-06-15 08:33:18

can this solved by Binary indexed tree 2-D???

Hermano: 2011-05-23 16:17:12

Too slow. How can I sum all elements of a matrix faster? I'm using Java. It looks like no one has solved this using java.

Ðộ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 !! ;)


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