Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Erik: The Candyboy - 2

By skmonir · Limits 1s, 512 MB

Now Erik has more candies than he had previously. In fact, he has infinite number of candies, and he wants to distribute some of those candies among his N friends. All of his friends are standing in a row and numbered 1 to N from left to right. Initially they don’t have any candy.

While distributing candies, Erik will first choose a non-empty segment of consecutive friends from the row and start giving candies from left to right of the chosen segment. The 1st(leftmost) friend of the segment will get 1 candy, 2nd friend will get 2 candies, 3rd friend will get 3 candies and so on.
More formally, he will choose a segment [L, R]. For each i such that LiR, the ith friend will get i - L + 1 candies.

Erik has hired you as an assistant for the candy distribution. He wants you to perform two types of operation in this task.

1 L R — Distribute the candies in segment [L, R] in the described way.
2 L R — Calculate the summation of all candies distributed so far in segment [L, R].

For each operation of second type, print the summation of the candies and make Erik impressed on you.

Input

The first line contains two integers N, Q (1N, Q105) — The number of friends and the number of operations.
Each of next Q lines contains either first or second type of operation.
First type of operation looks like 1 L R (1LRN).
Second type of operation looks like 2 L R (1LRN).

Output

For each operation of second type, print the summation of the candies.

Sample

InputOutput
5 5
1 1 5
1 2 4
2 1 4
1 3 5
2 1 5
16
27

Initially each of 5 friends has 0 candy. So it looks like — 0 0 0 0 0
After operation 1 1 50 0 0 0 0 → 1 2 3 4 5
After operation 1 2 4 — 1 2 3 4 5 → 1 3 5 7 5
For operation 2 1 41 3 5 7 5 → 1 + 3 + 5 + 7 = 16
After operation 1 3 5 — 1 3 5 7 5 → 1 3 6 9 8
For operation 2 1 51 3 6 9 8 → 1 + 3 + 6 + 9 + 8 = 27


Discussion

Statistics


61% Solution Ratio

RamprosadGEarliest, 4w ago

Riaz_BSMRSTUFastest, 0.1s

BrehamPieLightest, 1.6 MB

practiceboyShortest, 2205B

Submit

Login to submit