A11476. SUM and REPLACE

Let $D(x)$ be the number of positive divisors of a positive integer $x$ . For example, $D(2)=2$ ( $2$ is divisible by $1$ and $2$ ), $D(6)=4$ ( $6$ is divisible by $1$ , $2$ , $3$ and $6$ ).

You are given an array $a$ of $n$ integers. You have to process two types of queries:

1. REPLACE $l$ $r$ — for every  replace $a_{i}$ with $D(a_{i})$ ;
2. SUM $l$ $r$ — calculate .

Print the answer for each SUM query.

The first line contains two integers $n$ and $m$ ( $1<=n,m<=3·10^{5}$ ) — the number of elements in the array and the number of queries to process, respectively.

The second line contains $n$ integers $a_{1}$ , $a_{2}$ , ..., $a_{n}$ ( $1<=a_{i}<=10^{6}$ ) — the elements of the array.

Then $m$ lines follow, each containing $3$ integers $t_{i}$ , $l_{i}$ , $r_{i}$ denoting $i$ -th query. If $t_{i}=1$ , then $i$ -th query is REPLACE $l_{i}$ $r_{i}$ , otherwise it's SUM $l_{i}$ $r_{i}$ ( $1<=t_{i}<=2$ , $1<=l_{i}<=r_{i}<=n$ ).

There is at least one SUM query.

For each SUM query print the answer to it.