Description:


这天,lyk又和gcd杠上了。
它拥有一个 \(n\) 个数的数列,它想实现两种操作。

  1. \(a_i\) 改为 \(b\)
  2. 给定一个数 \(i\) ,求所有 \(gcd(i,j)=1\) 时的 \(a_j\) 的总和。

Input:


第一行两个数 \(n,Q\) ( \(1\le n,Q\le 100000\) )。
接下来一行 \(n\) 个数表示 \(a_i\) ( \(1\le a_i\le 10^4\) )。
接下来 \(Q\) 行,每行先读入一个数 \(A\) ( \(1\le A\le 2\) )。
\(A=1\) ,表示第一种操作,紧接着两个数 \(i\)\(b\) 。( \(1\le i\le n,1\le b\le 10^4\) )。
\(A=2\) ,表示第二种操作,紧接着一个数 \(i\) 。( \(1\le i\le n\) )。

Output:


对于每个询问输出一行表示答案。

Sample Input:


Sample Output:


题解:


我们先看第二种操作,相当于是求

\[\sum_{j=1}^n [gcd(i, j)=1]a_j\]

然后我们推式子,莫比乌斯反演一下,就变成了

\[\sum_{d|i}\mu (d) \sum_{j=1}^{\lfloor \frac{n}{d} \rfloor} a_{jd}\]

发现后面那一部分就是所有下标为 \(d\) 的倍数的数的和。

我们维护 \(sum[i]\) 表示所有下标为 \(i\) 的倍数的数的和,当更改某位置的时候枚举其约数维护 \(sum\) 数组。

貌似约数个数是 \(O(n^{\frac{1}{3}})\) 级别的,所以时间复杂度为 \(O(n\ln n + Q\times n^{\frac{1}{3}})\)