## Checkerboard Summation (Easy)

You are given a checkerboard with M rows and N columns (1 ≤ M,N ≤ 3000). Up to 100000 of these cells have specified values written in them, and the rest are zeroes. 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 answer up to 100000 queries of the form:

*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. Each line contains three space-separated integers R, C, and X (1 ≤ R ≤ M, 1 ≤ C ≤ N, -1000 ≤ X ≤ 1000), indicating that the value X is written in row R and column C. No cell will be given twice in the input. The last line is followed by a line containing three zeroes, signifying the end of this section of input.

Following this are a number of lines containing queries. Each line contains four space-separated integers: 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.

**Output**

Print the answer to each query on its own line, in order.

**Sample Input**

3 3

1 2 5

3 1 -2

2 3 11

0 0 0

2 1 3 3

0 0 0 0

**Sample Output**

13

**Explanation**

The checkerboard is three cells by three cells. Here's what it looks like:

0 5 0 0 0 11 -2 0 0

We are asked to find the alternating sum of the second and third rows. The 11 is in a square of the same colour as (2,1), so it is added; -2 is on a square of opposite colour, so it is subtracted. 11-(-2) = 13.

All Submissions

Best Solutions

**Point Value:** 12 (partial)

**Time Limit:** 2.00s

**Memory Limit:** 256M

**Added:** Dec 01, 2008

**Author:** bbi5291

**Languages Allowed:**

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

## Comments (Search)

Davo36on Mar 06, 2016 - 8:59:52 pm UTC Can this be done in Python?I have got it going, and get the correct result when submitting for the first 4 set of tests. But then run out of time after that.

I am using Python 3 and have a DP approach (can't be sure it's the optimal one, but it seems fairly sensible to me).

I have looked through the accepted solutions and they are all in C, C++ or Java. I don't see any Python solutions.

So my question is, can Python be used? Or is it just too slow?

Davo36on Mar 07, 2016 - 2:31:15 am UTC Re: Can this be done in Python?Same strategy as Python, but of course it runs so much faster.

bbi5291on Dec 17, 2008 - 3:03:27 am UTC HintdAedaLon Dec 02, 2008 - 3:48:40 am UTCFour?

bleung91on Dec 02, 2008 - 4:59:01 am UTC Re:1 2 5

3 1 -2

2 3 11

This is the checkerboard values.

0 0 0

This tells you the checkerboard values are finished inputting.

2 1 3 3

0 0 0 0

The first line is input for which you have to output an answer, and the 0 0 0 0 tells you it is done inputting.

dAedaLon Dec 02, 2008 - 12:17:54 pm UTC Re: Re:bbi5291on Dec 01, 2008 - 3:22:06 pm UTC This is an easier problem.How does this make the problem easier?