### 问题描述 GCD 是最大公约数的英文缩写，全称为 Greatest Common Divisor。在数学中，最大公约数指的是几个自然数或整数的公共约数中最大的一个。例如，$12$ 和 $18$ 的最大公约数是 $6$，因为 $12$ 和 $18$ 都可以被 $6$ 整除，而且没有比 $6$ 更大的公约数。最大公约数在数学、计算机科学等领域有着广泛的应用。 小郑对 GCD 有着独特的理解，并发明了一种超级 GCD 转换方法。 对于一个整数 $X$，超级 GCD 会将 $X$ 转换为：集合 $[i \mid 1 \le i \le X \wedge \gcd(i,X)=1]$ 的大小。 现在给出一个大小为 $N$ 的数组，小郑可以对这个数组进行两种操作。 1. 对 $L-R$ 的数做一次超级 GCD 转换。 2. 查询 $L-R$ 的和。 ### 输入格式 首先第 $1$ 行是 $2$ 个整数 $N$、$Q$，分别代表数组的长度和操作的次数。 第 $2$ 行输入 $N$ 个整数，表示数组的 $N$ 个元素，数组从 $1$ 开始编号。 接下来 $Q$ 行，每行代表 $1$ 个操作。 每行输入 $3$ 个整数 $M$、$L$、$R$。 如果 $M == 1$，进行操作 $1$，对 $L$ 到 $R$ 的数做一次超级 GCD 转换。 如果 $M == 2$，进行操作 $2$，查询 $L$ 到 $R$ 的和。 ### 输出格式 对于每一个操作 $2$，输出数组在 $L$ 到 $R$ 的和。 ### 样例输入 ```text 5 5 1 2 3 4 5 1 1 2 2 1 5 1 3 5 1 4 5 2 2 3 ``` ### 样例输出 ```text 14 3 ``` ### 样例说明 设变换函数为 $F(x)$。 - $F[1]=[1]$ - $F[2]=[1]$ - $F[3]=[1,2]$ - $F[4]=[1,3]$ - $F[5]=[1,2,3,4]$ 执行了第 $1$ 条操作后数组变成了 $[1，1，3，4，5]$。 执行了第 $2$ 条操作后输出 $1+1+3+4+5=14$。 执行了第 $3$ 条操作后数组变成了 $[1，1，2，2，4]$。 执行了第 $4$ 条操作后数组变成了 $[1，1，2，1，2]$。 执行了第 $5$ 条操作后输出 $1+2=3$。 ### 评测数据规模 对于所有评测数据，$0 \lt N,Q \lt 100$，$0 \lt Arr[i] \lt 10^5$，$0 \lt L,R \le N$。