Problem Description

Teacher Mai finds that many problems about arithmetic function can be reduced to the following problem:

Maintain an array a with index from 1 to l. There are two kinds of operations:

1. Add v to ax for every x that gcd(x,n)=d.
2. Query 



There are multiple test cases, terminated by a line “0 0”.

For each test case, the first line contains two integers l,Q(1<=l,Q<=5*10^4), indicating the length of the array and the number of the operations.

In following Q lines, each line indicates an operation, and the format is “1 n d v” or “2 x” (1<=n,d,v<=2*10^5,1<=x<=l).



For each case, output “Case #k:” first, where k is the case number counting from 1.

Then output the answer to each query.


Sample Input
6 4 1 4 1 2 2 5 1 3 3 3 2 3 0 0


Sample Output
Case #1: 6 7






We have carefully selected several similar problems for you:  6297 6296 6295 6294 6293
考虑定义$a_i=\sum\limits_{d|i}^{n} f(d)$ 那么考虑题意中一个v需要加到哪几个$a_i$ 在原式中:$a_x+=v\times[gcd(x,n)=d]=v\times[gcd(x/d,n/d)=1]$ 然后可以套路反演一下$a_x+=v\times \sum\limits_{p|\frac{n}{d},p|\frac{x}{d}}\mu(p)$ 那么我们发现枚举$\frac{n}{d}$的所有约数的d倍就是我这次添加操作会影响的关于$a_x$的那些f数组的位置 所以添加$f(pd)+=v*\mu(p)$ 我们询问一个点$a[x]=\sum\limits_{d|x}f(d)$ $\sum\limits_{i=1}^{x}\sum\limits_{d|i}f(d)$可以枚举d $\sum\limits_{d=1}^{x}\frac{x}{d}f(d)$针对$\frac{x}{d}$数论分块即可 然后树状数组求前缀和 查询的时候树状数组求和即可



退役了 现在在商院 偶尔打CF,有时有ACM regional也去玩一下