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
GURVINDER SINGH: 2014-06-05 13:46:26

AC With long long wa with int o.O

zicowa: 2014-04-20 12:26:08

@those who are getting WAs . put a newline after each test case or use only int not long long .if this does not work then check your code again probably mistake is there.

Olli Forty: 2014-01-17 16:32:23

As Ihtisham, I am getting error(SIGSEGV) although code runs fine on ideone. Can you please provide an example with two test cases? (This would also clarify the blank line issue).

Savan Popat: 2014-01-02 09:47:52

strange TLE with long long. changed to int and AC :). anyway nice question. learned 2D-BIT

Last edit: 2014-01-02 09:48:20
code quá nhanh ...: 2013-12-18 15:29:33

NO blank line between the tests!! costs me some WAs

aqfaridi: 2014-01-02 09:48:47

use fast i/o ..

Surya kiran: 2014-01-02 09:48:38

what are the constraints for t?

chansiddharth: 2012-11-25 20:15:31

BIT 2D worked fine for me .I used I/O methods faster than cin and cout .

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?


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