# 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

hujie

## Source

BestCoder Round #73 (div.1)