CF920F.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.

令 $D(x)$ 表示正整数 $x$ 的正因数个数。例如，$D(2) = 2$（2 能被 1 和 2 整除），$D(6) = 4$（6 能被 1、2、3 和 6 整除）。

给定一个包含 $n$ 个整数的数组 $a$。你需要处理两类查询：

1. REPLACE l r — 对每个 $i \in [l, r]$，将 $a_i$ 替换为 $D(a_i)$；
2. SUM l r — 计算 $\sum\limits_{i=l}^{r} a_i$。

对每个 SUM 查询，输出其结果。

The first line contains two integers n and m (1 ≤ n, m ≤ 3·105) — 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 ≤ 106) — 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.

第一行包含两个整数 $n$ 和 $m$（$1 \leq n, m \leq 3 \cdot 10^5$），分别表示数组的元素个数以及需要处理的查询个数。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \leq a_i \leq 10^6$），表示数组的元素。

接下来是 $m$ 行，每行包含三个整数 $t_i, l_i, r_i$，表示第 $i$ 个查询。若 $t_i = 1$，则第 $i$ 个查询为 REPLACE $l_i$ $r_i$；否则为 SUM $l_i$ $r_i$（$1 \leq t_i \leq 2$，$1 \leq l_i \leq r_i \leq n$）。

至少存在一个 SUM 查询。

For each SUM query print the answer to it.

对于每个 SUM 查询，输出其答案。