# hdu5634

Rikka with Phi

### decription

Rikka and Yuta are interested in Phi function (which is known as Euler’s totient function).
Yuta gives Rikka an array A[1..n] of positive integers, then Yuta makes m queries.
There are three types of queries:

1lr
Change A[i] into φ(A[i]), for all i∈[l,r].

2lrx
Change A[i] into x, for all i∈[l,r].

3lr
Sum up A[i], for all i∈[l,r].
Help Rikka by computing the results of queries of type 3.

### input

The first line contains a number T(T≤100) ——The number of the testcases. And there are no more than 2 testcases with \$n>10^5\$
For each testcase, the first line contains two numbers n,m(\$n≤3×10^5,m≤3×10^5\$)。
The second line contains n numbers A[i]
Each of the next m lines contains the description of the query.
It is guaranteed that \$1≤A[i]≤10^7\$ At any moment.

### output

For each query of type 3, print one number which represents the answer.

### sample input

1
10 10
56 90 33 70 91 69 41 22 77 45
1 3 9
1 1 10
3 3 8
2 5 6 74
1 1 8
3 1 9
1 2 10
1 4 9
2 8 8 69
3 3 9

80
122
86

### toturial

phi函数求不了几次就会变成1,区间修改只会让区间值变化为相同，两个修改都逐渐让区间值变成相同。所以可以用线段树维护一个区间最大值，一个区间最小值，当区间最大值等于区间最小值的时候，我们可以把求phi操作对整个区间一起做了。

目录