Rikka with Phi

Time Limit: 16000/8000 MS (Java/Others)

Memory Limit: 131072/131072 K (Java/Others)

Description

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:

$ 1 \; l \; r $

Change $A[i]$ into $\varphi(A[i])$, for all $i \in [l, r]$.

$ 2 \; l \; r \; x$

Change $A[i]$ into $x$, for all $i \in [l, r]$.

$ 3 \; l \; r $

Sum up $A[i]$, for all $i \in [l, r]$.

Help Rikka by computing the results of queries of type 3.

Input

The first line contains a number $T(T \leq 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 \leq 3 \times 10^5, m \leq 3 \times 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 \leq A[i] \leq 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

Sample Output

80 122 86

Hint

hujie

Source

BestCoder Round #73 (div.1)

提交代码