It is now Griffy's turn to hide! Unfortunately, he has strayed a bit too far and has found himself trapped in an ice cave (what are the odds?). Griffy was getting very lonely, so he decided to make friends with all the stalactites in there! The cave is by coincidence a perfect cube . The cube can be thought of as a series of coordinates, where the coordinates are in the range to . At each set of integer coordinates, one stalactite can be found. As an icebreaker, Griffy decides to count the sum of the lengths of all the stalactites inside a rectangular volume. The game gets harder though, as each stalactite can change in length. Given the changing conditions, help Griffy master this game. You can assume that no stalactite changes length while Griffy is counting the sum. Stalactites all start with the same length of . You can also assume that the length of a stalactite at any point will always be a non-negative integer less than or equal to .

**Note:** At least 30% of the test cases will have all the change length commands coming before the sum commands.

#### Input Specification

First line: , the size of the cubic cave.

Second line: , the number of events (changing stalactite length, or sum of prism).

The next lines are each in the form of:

The stalactite in the coordinate of has changed to a length of .

Find the sum of the stalactites in the rectangular prism bounded by the corners and .

#### Output Specification

One line, **the sum of all of the sum queries**.

#### Sample Input

```
2
5
C 1 1 2 5
C 1 2 2 5
C 2 1 2 5
S 1 1 1 2 2 2
S 1 1 2 1 1 2
```

#### Sample Output

`20`

#### Explanation for Sample Output

The answer to the first sum query is , and the answer to the second one is .

## Comments

It's not that strict for java ... Just watch some details ^^

Submissions with correct algorithm in Java can't pass in time (tested by resubmitting jeffreyxiao's 100/100 submission several times).

Edit: It passes now.

Is it even possible to do this with languages like java without exceeding the 256 MB mem limit?

Yes; an unoptimized solution translated from C++ passes just in time (http://www.dmoj.ca/submission/67640).

270mb is used in the max case, but while we display the total VM memory,

heap space is used to determine MLE(and the heap is smaller, just slightly, than 256mb).You'll want to use

`BufferedReader`

or similar for input:`Scanner`

passes through sheer luck in 4.998 seconds for max case.If it is THAT close, then why not just increase the memory limit by a little bit?

Why? It's perfectly passable in C++. If you can't pass in Java, sucks to be you.

This comment is hidden due to too much negative feedback. Show it anyway.

other languages exist outside the competitive programming atmosphere

k thanks for clearing up.