## Checkerboard Summation (Hard)

You are given a checkerboard with M rows and N columns (1 ≤ M,N ≤ 3000). Each square initially has the number zero written in it. For top-secret strategic reasons which are given out on a need-to-know basis only (and you do not, at the present moment, need to know) you must write a program that will perform two types of operation:*Modify*: Given the row and column of a square on the checkerboard, change the number written in it to a new value.

*Query*: Given the coordinates of two squares on the checkerboard, find the alternating sum of all of the numbers within the rectangle delimited by those two squares. By alternating sum what is meant is that we add all numbers in squares with the same colour as the first square given, and subtract all numbers with the opposite colour.

### Input

The first line of the input file contains the integers M and N.A number of input lines then follow. The integer at the beginning of the line signifies:

**0**: End of input.

**1**: A modify operation. Three integers follow: R, C, and X (1 ≤ R ≤ M, 1 ≤ C ≤ N, -1000 ≤ X ≤ 1000), indicating that the value X is to be written in row R and column C.

**2**: A query. Four integers follow: R1, C1, R2, and C2 (1 ≤ R1 ≤ R2 ≤ M, 1 ≤ C1 ≤ C2 ≤ N). Output the alternating sum of all squares contained within the box [R1,R2] × [C1,C2], as described.

There will never be more than 100000 commands given.

### Output

For each query operation, print the answer on its own line.### Sample Input

3 3 1 1 2 5 1 3 1 -2 2 1 1 2 3 1 2 3 11 2 2 1 3 3 0

### Sample Output

-5 13

### Explanation

The checkerboard is three cells by three cells. When the first query is executed, the board looks like this:

0 5 0 0 0 0 -2 0 0

We are asked to find the alternating sum of the first two rows. Since the 5 is on a square of opposite colour to the first square, it is subtracted to obtain an answer of -5. For the second query, the board looks like:

0 5 0 0 0 11 -2 0 0

Now, we take the alternating sum of the second and third rows. 11 is added, whereas -2 is subtracted, to give the answer 13.

All Submissions

Best Solutions

**Point Value:** 25 (partial)

**Time Limit:** 1.00s

**Memory Limit:** 256M

**Added:** Oct 19, 2008

**Author:** bbi5291

**Problem Types:**[Show]

**Languages Allowed:**

C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

## Comments (Search)

DannyYangon Aug 05, 2017 - 7:08:14 pm UTC Stupid test caseFatalEagleon Jan 17, 2014 - 4:08:16 am UTC Test Data Inconsistencychecker5.in -- first occurrence line 6951 R2>M

checker6.in -- first occurrence line 10253 X>1000

checker7.in -- first occurrence line 13977 C>N

checker8.in -- first occurrence line 1734 R2>M

checker9.in -- first occurrence line 11125 C2>N

If you bounded your BIT/FT with 3000, 3000 instead of M, N then you'll get WA.

Paradoxon May 25, 2016 - 5:51:04 am UTC Re: Test Data InconsistencyBecause I'm getting WA for #7 and #9

thomas0115on May 27, 2016 - 8:11:48 pm UTC Re: Test Data InconsistencyXue_Alexon Aug 01, 2017 - 12:00:42 am UTC Re: Test Data Inconsistencybbi5291on Dec 07, 2008 - 7:29:21 pm UTC Hint