SUM and REPLACE

- 给定 $n$ 个数的数组 $a$，$m$ 次操作。操作有两种： 1. 将 $i\in[l,r]$ 中的所有 $a_i$ 替换为 $d(a_i)$。$d(x)$ 表示 $x$ 的正约数的个数。 2. 求 $\displaystyle\sum_{i=l}^r a_i$。 - $1\le n,m\le 3\times 10^5$，$1\le a_i\le 10^6$。

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.

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

30
13
4
22