题目描述

十一黄金周去 qbxt 浪了一个礼拜之后，dkw 终于要月考了！

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

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

dkw 给每个题目算出来了一个预估值 $A_i$。

具体来说，有四种操作：

• L x y p：表示 dkw 询问 $[x,y]$ 的 $\text{lcm}$ 对 $p$ 取模之后的值；
• G x y p：表示 dkw 询问 $[x,y]$ 的 $\gcd$ 对 $p$ 取模之后的值；
• C x y c：表示 dkw 改变了 $[x,y]$ 的预估值，统一为 $c$；
• S x y p：表示 dkw 询问 $[x,y]$ 的公因数个数对 $p$ 取模之后的值。

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

输入格式

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

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

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

输出格式

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

样例

input

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

output

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,q\le 10^5$，保证没有修改操作；
对于 $100\%$ 的数据，$1\le n,q\le 3\times 10^5$；
保证任何时刻每个题目的预估值都在 $[1,100]$ 之间，答案取模之后不超过 int。