Tropical Bananas

View as PDF

Points: 10 (partial)
Time limit: 2.0s
Memory limit: 256M

Authors:
Problem types

The Tropical Banana, also known as the Musa verylongnamea, is a delicacy known all over the otherworld. However there is one thing about the Musa verylongnamea that most people do not know: this specific type of banana is extremely picky and will refuse to grow unless heaps and heaps of fertilizer are dumped all over the place it grows, a place known as The Infernal Isles.

With the early retirement of the previous Keeper of Bananas, Florence has been chosen to groom those bananas to perfection. This would normally be an extremely joyous event because of the exorbitant pay, however, there are two problems: she has no idea how to fertilize Tropical Bananas, and each spray of the TURF BUILDER 999 PRO launches layers of fertilizer all over the place. The Infernal Isles is made up of separate columns of soil, each originally starting with layers of fertilizer. Florence can do one of two tricks with the TURF BUILDER 999 PRO: she can spray column to , adding layers to column , layers to column , and so on until column where she adds layers. Otherwise, she can do the opposite, spraying column to and adding layers to column , layers to column and so on until column where she adds layers. Specifically, there are two operations where:

0 l r a b - for all between and inclusive, increase by .

1 l r a b - for all between and inclusive, increase by .

In fact, the TURF BUILDER 999 PRO is so powerful that it can remove layers of fertilizer and may even cause some columns to have a negative amount of layers of fertilizer! Don't ask what this means, since Florence doesn't know either. She needs to record the number of layers of fertilizer at each column in order to efficiently grow Tropical Bananas, but unfortunately speed math is not her strong suit. Desperate, she asks you, a world renowned Scratch programmer to help her calculate the number of layers of fertilizer at each column after she sprays fertilizer times.

For this problem, Python users are recommended to use PyPy over CPython.

Input Specification

The first line will contain two integers and , representing the number of columns and the number of operations respectively.

Each of the next lines will contain an operation in the form of , , , and where is either or .

Output Specification

Output lines, the line containing the value of after all the operations have been applied.

Sample Input 1

4 5
1 1 4 9 0
1 2 4 10 -7
0 1 2 4 6
0 2 3 3 -9
0 2 3 5 -1

Sample Output 1

19
12
-7
12

Explanation for Sample 1

The first operation adds to all the elements between index and inclusive. The second operation adds to index , to index and to index . The third operation adds to index and to index . Doing all the operations will result in a final list of numbers: , , and .

Sample Input 2

4 5
0 2 4 45 73
1 3 4 61 -10
0 2 4 96 86
1 4 4 27 23
0 1 2 12 48

Sample Output 2

60
408
500
719

Explanation for Sample 2

The first operation adds to index , to index and to index . The second operation adds to index and to index . Doing all the operations will result in a final list of numbers: , , and .