A93496.求和与替换

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

给定一个包含 $n$ 个整数的数组 $a$。你需要处理两种类型的操作：

1. REPLACE $l$ $r$：对于每一个 $l\le i\le r$，将 $a_i$ 替换为 $D(a_i)$；
2. SUM $l$ $r$：计算 $\sum_{i=l}^{r} a_i$。

每次 SUM 操作需要输出结果。

第一行包含两个整数 $n$ 和 $m$（$1\le n,m\le 3\cdot 10^5$）。

第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$（$1\le a_i\le 10^6$）。

接下来 $m$ 行，每行包含 $3$ 个整数 $t_i,l_i,r_i$：

• 若 $t_i=1$，表示 REPLACE $l_i$ $r_i$
• 否则表示 SUM $l_i$ $r_i$

保证至少有一次 SUM 操作。

对于每个 SUM 操作，输出一行结果。

样例解释

• 第一次 SUM：$6+4+1+10+3+2+4=30$
• 第二次 SUM：$10+3=13$
• 执行一次 REPLACE(3,5) 后：把 $a_3,a_4,a_5$ 替换成它们的约数个数
• 后面同理，按操作顺序计算即可