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 ~\Bigl\lfloor \dfrac{A_i}{i} \Bigr\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 2\,000~

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 ~\Bigl\lfloor \dfrac{A_i}{i} \Bigr\rfloor~ for ~1 \le i \le 8~ is ~1+2+1+0+0+0+0+0 = 4~.