题目描述
定义一个数的漂亮值为 f(x)f(x)f(x) ,(xxx 为正整数)。
x>1x>1x>1 时, f(x)=Σi=1kpi f(x)=\Sigma_{i=1}^{k}{p_i}\f(x)=Σi=1kpi ,且 a1p1×a2p2×...×akpk=xa_1^{p_1}\times{a_{2}^{p_{2}}}\times...\times{a_{k}^{p_{k}}} = xa1p1×a2p2×...×akpk=x , 同时 a1,a2...aka_1,a_2...a_ka1,a2...ak 全为质数 ;
x=1x=1x=1 时, f(x)=0f(x) =0f(x)=0 。
有一个段长为 nnn 的整数序列 , 第 iii 个数为 bib_ibi。
有以下两个操作:
opt1:opt_1:opt1: 给定两个数 lll , rrr 输出 f(Πi=lrbi)f(\Pi_{i=l}^{r}{b_i})f(Πi=lrbi) 。
opt2opt_2opt2 ::: 给定三个数 lll , rrr , www 让所有 bj=bj×w(l≤j≤r)b_j=b_j\times w ( l \le j \le r)bj=bj×w(l≤j≤r) 。
输入
第一行一个整数 nnn (1≤n≤105)(1 \le n \le 10^5)(1≤n≤105) 。
第二行 nnn 个整数,第 iii 个整数 bib_ibi (1≤bi≤4×106)(1 \le b_i \le 4 \times10^6)(1≤bi≤4×106) 。
第三行一个整数 qqq (1≤q≤105)(1 \le q \le 10^5)(1≤q≤105) 。
接下来 qqq 行,
第一个整数 optoptopt (opt∈{1,2})(opt \in {\{1,2\}})(opt∈{1,2}),
opt=1opt = 1opt=1 时,后面两个整数 lll , rrr (1≤l≤r≤n)( 1\le l \le r\le n)(1≤l≤r≤n) , 并且执行操作 111 。
opt=2opt = 2opt=2 时,后面三个整数 lll , rrr , www (1≤w≤4×106,1≤l≤r≤n)(1 \le w \le 4\times10^6,1\le l\le r \le n)(1≤w≤4×106,1≤l≤r≤n), 并且执行操作 222 。
输出
每次询问输出一行一个整数,表示询问的结果
样例输入 Copy
5
2 2 3 4 5
3
1 1 3
2 1 2 2
1 1 3
样例输出 Copy
3
5
提示
第一次操作 , 询问区间 [1,3][1,3][1,3] ,f(Πi=13bi)=f(12)=f(22×3)=3f(\Pi_{i=1}^{3}{b_i}) = f(12) = f(2^2\times3) = 3f(Πi=13bi)=f(12)=f(22×3)=3 , 所以第一行输出 333 。
第二次操作 , 更改区间 [1,2][1,2][1,2] , 更改后序列变为 444 , 444 , 333 , 444 , 555 。