A21670.公主の#19准备月考

省选/NOI-

通过率：0%

时间限制：1.00s

内存限制：128MB

公主在玩完游戏后，也要月考了。（就算是公主也要月考啊QWQ）
公主的文综太差了，全校排名1100+（全校就1100多人），她分析了好久，发现她如果把所有时间放在选择题上，得分会比较好一点。

文综题目共有n个，编号从1到n

公主给每个题目算出来了一个预估值Ai，她认为，一段连续题目的答案会在它们的预估值的gcd和lcm之间；有时候她的想法不同了，一些题目的预估值会改变；有时候，会出现多选题，多选题的答案数量就是一段连续题目答案的预估值的公约数的个数。

具体来说，对于一个数列，有四种操作：

L x y p 表示公主询问区间[x,y]的数字的lcm对p取模之后的值

G x y p 表示公主询问区间[x,y]的数字的gcd对p取模之后的值

C x y c 表示公主改变区间[x,y]的数字的值，统一为c

S x y p 表示公主询问区间[x,y]的数字的公因数个数对p取模之后的值

公主月考不能挂科，不然她就不能学习OI了（假的），所以请你帮帮她吧！

第一行，两个正整数n和q，q表示操作次数

第二行，n个正整数，表示dkw对题目的预估值

接下来q行，每行输入一个操作，格式详见题目描述

对于每个询问，输出它的答案。

输入#1

10 10
42 68 35 1 70 25 79 59 63 65 
L 2 6 28
L 2 6 43
G 2 7 5
G 3 4 83
L 7 9 96
G 2 7 39
S 3 8 100
L 4 5 12
G 4 4 65
L 2 4 69

输出#1

对于30%的数据，1<=n,q<=1000

对于另外20%的数据，1<=n<=1000，1<=q<=100000

对于另外20%的数据，1<=n<=100000，1<=q<=100000，保证没有修改操作

对于100%的数据，1<=n<=300000，1<=q<=300000

保证任何时刻每个题目的预估值都在[1,100]之间，答案取模之后不超过int