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 L ≤ i ≤ R, 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 (1 ≤ N, Q ≤ 105) — 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 (1 ≤ L ≤ R ≤ N).
Second type of operation looks like 2 L R (1 ≤ L ≤ R ≤ N).
Output
For each operation of second type, print the summation of the candies.
Sample
| Input | Output |
|---|---|
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 | |
