Background

qwqwq

Description

When qwq plays with the Legend of Hearthstone, he can't always use "defile" well, so he created a simplified version of this game, and changed the description of "defile": "Select an integer in [L, R] uniform randomly as the damage value $d$, to cause $d$ points of damage (i.e. decrease their HP by $d$) to all minions. If any minion dies(i.e. HP $\le$ 0), cast the spell again, but the damage value is still $d$; if no minion dies, stop."

Qwq didn't know the effect of this new version of defile, so he planned to carry out some tests, including M operations of the following types:

1. Add a minion with HP of $h$, where the minion's HP cannot exceed $n$;
2. Given $L,R$, query how many times the "defile" is expected to trigger;

Your task is to help qwq to simulate these operations, and calculate the answer of each operation 1.

Input Format

Read from standard input.

In the first line there are two integers $n\;m$. In the next $m$ lines, each line contains an operation, represented by $1\;h$ (operation 1) or $2\;L\;R$ (operation 2).

Output Format

Write to the standard output.

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

Sample

Input

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

3
8
11
6

Subtasks

Subtask 1: $n,m \le 10^3$.

Subtask 2: In operation 2, $L=R$.

Subtask 3: All operation 2 come after operation 1.

Subtask 4: $m\le 10^5$.

Subtask 5: No extra constraint.

Each subtask above is worth 19pts, and Subtasks 1 to 4 are mutually disjoint.

For all of the test cases:

• $1\le n\le 10^5$
• $1\le m\le 10^6$
• In each operation 1: $1\le h\le n$
• In each operation 2: $1\le L\le R\le n$
• All of the parameters above are integers.