#3853. GCD Array

题目描述

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 Sigma(Xi) (i<=1<=X)

输入格式

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.

样例

样例输入

6 4  

1 4 1 2  

2 5  

1 3 3 3  

2 3  

0 0

样例输出

Case #1:  

6  

7

数据范围与提示