← 返回题目列表

Codeforces · 920/F

F. 求和并替换

中文机器翻译题面 查看原题

设 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