设 D(x) 为正整数 x 的正约数数。例如,D(2) = 2(2 可被 1 和 2 整除),D(6) = 4(6 可被 1、2、3 和 6 整除)。
给定一个包含 n 个整数的数组 a。您必须处理两种类型的查询:
1. REPLACE l r — 对于 [l, r]$$ 中的每个 $$i \in,将 ai 替换为 D(ai);
2. SUM l r — 计算 $$\sum_{i=l}^{r}a_i$$。
打印每个 SUM 查询的答案。
输入
第一行包含两个整数 n 和 m (1 ≤ n, m ≤ 3·105) — 分别是数组中的元素数量和要处理的查询数量。
第二行包含 n 个整数 a1, a2, ..., an (1 ≤ ai ≤ 106) — 数组的元素。
接下来是 m 行,每行包含 3 个整数 ti、li、ri 表示第 i 个查询。如果 ti = 1,则第 i 个查询为 REPLACE li ri,否则为 SUM li ri (1 ≤ ti ≤ 2, 1 ≤ li ≤ ri ≤ n)。
至少有一个 SUM 查询。
输出
对于每个 SUM 查询,打印其答案。
示例
输入 #1
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
输出 #1
30 13 4 22