P4256 公主の#19准备月考

公主在玩完游戏后，也要月考了。（就算是公主也要月考啊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$ 行，每行输入一个操作，格式详见题目描述。

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

对于 $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`。