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操作对整个区间一起做了。 第二点，这个问题如果用splay将达到更高的效率，区间赋值的时候，我们直接在splay上删除原区间，用一个节点代替，求phi同理，跑起来飞快

### code-splay

-----------------------本文结束感谢您的阅读-----------------------