SUM and REPLACE

Source: Codeforces

Version: Phuoc Hung OJ Extended

Problem Statement

Let $D(x)$ be the number of positive divisors of positive integer $x$. Given $a_1,\ldots,a_n$, process $m$ operations:

• 1 l r: for every $i\in[l,r]$, set $a_i\leftarrow D(a_i)$.
• 2 l r: print the sum of the elements in $[l,r]$.

Input

The first line contains $n,m$. The second line contains the array. Each of the next $m$ lines contains t l r, where t=1 is REPLACE and t=2 is SUM.

Output

For every type-2 operation, print the range sum on its own line.

Subtasks

• Subtask 1 (20%): n,m≤30; all other conditions are unchanged.

• Subtask 2 (30%): n,m≤3000; all other conditions are unchanged.

• Subtask 3 (50%): full constraints:

• $1\le n,m\le3\cdot10^5$

• $1\le a_i\le10^6$

• there is at least one type-2 query

Examples

Input

7 6
6 4 1 10 3 2 4
2 1 7
2 4 5
1 3 5
2 4 4
1 5 7
2 1 7

Output

30
13
4
22

Explanation

Initially the whole-array sum is 30. Replacing positions 3..5 by their divisor counts changes 1,10,3 into 1,4,2; therefore the single-position sum at 4 is 4.