You are given an array $A$ of size $N$, with all elements initially equal to $0$. Support the following operations:

• Type 1: Given $l$ and $r$, increment all $A_i$ with $l\le i\le r$ by $1$.
• Type 2: Given $l$ and $r$, return the sum of all $\lfloor {\displaystyle \frac{A_i}{i}}\rfloor$ for $l\le i\le r$.

Constraints

For all subtasks:

$1\le N\le {10}^9$

$1\le Q\le 2\times {10}^5$

$1\le t_i\le 2$

$1\le l_i\le r_i\le N$

Subtask 1 [20%]

$1\le N,Q\le 2000$

Subtask 2 [80%]

No additional constraints.

Input Specification

The first line contains $2$ integers $N$ and $Q$, the size of the array and the number of operations to be performed.

The next $Q$ lines each contain $3$ integers $t_i,l_i,r_i$ $(1\le i\le Q)$, the type number of the $i^{th}$ operation and the parameters $l$ and $r$ for that operation.

Output Specification

For each operation of type $2$ output an integer on its own line, the return value of the operation.

Sample Input

8 8
2 1 8
1 1 4
2 1 2
2 2 8
1 2 3
1 2 7
1 2 8
2 1 8

Sample Output

0
1
0
4

Explanation

Right before the last operation, $A=[1,4,4,3,2,2,2,1]$. The sum of all $\lfloor {\displaystyle \frac{A_i}{i}}\rfloor$ for $1\le i\le 8$ is $1+2+1+0+0+0+0+0=4$.