题目背景

公主在玩完游戏后，也要月考了。（就算是公主也要月考啊QWQ）

题目描述

公主的文综太差了，全校排名 $1100$+（全校就 $1100$ 多人），她分析了好久，发现她如果把所有时间放在选择题上，得分会比较好一点。

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

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

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

• L x y p：表示公主询问区间 $[x,y]$ 的数字的 $\operatorname{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$，其中 $n$ 表示题目个数，$q$ 表示操作次数。

第二行，$n$ 个正整数，表示公主对题目的预估值。

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

输出格式

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

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

0
32
1
1
75
1
1
10
1
34

提示

对于 $30\%$ 的数据，$1\le n,q\le 1000$。

对于另外 $20\%$ 的数据，$1\le n\le 1000，1\le q\le 10^5$。

对于另外 $20\%$ 的数据，$1\le n\le 10^5，1\le q\le 10^5$，保证没有修改操作。

对于 $100\%$ 的数据，$1\le n\le 3\times 10^5，1\le q\le 3\times 10^5$。

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