

Rikka with PhiTime Limit: 16000/8000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)Total Submission(s): 3129 Accepted Submission(s): 792 Problem 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
Sample Output
Source  
