问题描述
给出一个长度为$n$的数组$A$，接下来有$m$次操作。
$ 1 \; l \; r $
对所有区间$[l,r]$中的整数$i$，把$A_i$变成$\varphi(A[i])$(指欧拉函数)
$ 2 \; l \; r \; x$
对所有区间$[l,r]$中的整数$i$，把$A[i]$变成$x$
$ 3 \; l \; r $
询问$[l,r]$的区间和。
输入描述
第一行一个整数 $T(T \leq 100)$ 表示数据组数，其中 $n > 10^5$ 的数据不超过 $2$ 组。
每组数据第一行两个整数 $n,m(n \leq 3 \times 10^5, m \leq 3 \times 10^5)$。
接下来一行 $n$ 个整数描述数组 $A$。
接下来$m$行, 每行若干个整数表示一次操作。
保证在任意时刻 $1 \leq A[i] \leq 10^7$。
输出描述
对于每一次询问输出一行，代表这个询问操作的答案。
输入样例
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
