Chtholly is always unable to play a textbook "Defile" while playing Hearthstone, so she rewrote a version of "Hearthstone'" and changed the description of "Defile" to: "Choose an integer $d$ from $[L, R]$ uniformly at random as the damage value, and deal $d$ damage to all minions. If any minion dies, cast this spell again, but the damage value $d$ is not re-randomized. If no minion dies, stop casting." She also removed the limit on the number of minions on the board and the 14-cast limit for "Defile".

Chtholly does not know how effective this modified "Defile" is, so she plans to conduct some tests, consisting of $m$ operations of the following types:

1. Add a minion with health $h$ to the board, where the health of any minion cannot exceed $n$.
2. Given $L$ and $R$, ask for the expected number of times "Defile" will be triggered.

Chtholly only knows how to perform operation 1, so she has left operation 2 to you.

Input

The first line contains two space-separated integers $n$ and $m$.

The next $m$ lines each represent an operation. Operation 1 is represented as $1\;h$, and operation 2 is represented as $2\;L\;R$.

Output

To avoid outputting decimals, for each operation 2, output an integer representing the product of the expected value and $(R-L+1)$.

Examples

Input 1

10 10
2 7 9
1 6
2 7 10
1 10
1 7
2 7 10
1 7
1 1
2 6 7
1 4

Output 1

3
8
11
6

Note

Idea: oscar, Solution: ccz181078, Code: ccz181078, Data: nzhtl1477

For $100\%$ of the data, it is guaranteed that: $1\le n\le 10^5$, for each operation 1, $1\le h\le n$, and for each operation 2, $1\le L\le R\le n$; $1\le m\le 10^6$; All values above are integers.