#P3853. GCD Array

    ID: 3056 传统题 6000ms 64MiB 尝试: 407 已通过: 106 难度: 7 上传者: 标签>CF2200提高+/省选-莫比乌斯反演树状数组整除分块交换求和顺序线性筛倍数枚举By镇海中学

GCD Array

Description

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

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

  • Add vv to axax for every xx that gcd(x,n)=dgcd(x,n)=d.
  • Query Sigma (XiX_i) (i≤1≤X)(i \le 1 \le X)

Input

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

For each test case, the first line contains two integers ll , QQ (1≤l,Q≤5∗104)(1 \le l,Q \le 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 "11 nn dd vv" or "22 xx" (1≤n,d,v≤2∗105,1≤x≤l)(1 \le n,d,v \le 2*10^5,1 \le x \le l).

Output

For each case, output "Case #k:" first, where kk is the case number counting from 11.

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