题目描述

大笨龙讨厌数学题，于是把题扔给聪明兔做。

聪明兔讨厌数学题，于是把题扔给你做。

给定一个长度为 $N$ 的序列 $a$ 和 $M$ 个指令。 每条指令都可能是以下两种形式之一：

• C l r d：把 $a_l,a_(l+1),...,a_r$ 都加上 $d$；
• Q l r：询问 $a_l,a_(l+1),...,a_r$ 的最大公约数。 对每个询问输出一个整数表示答案。

输入格式

第一行两个整数 $N,M$。

第二行 $N$ 个整数，分别表示 $a_1,a_2,...,a_N$。

接下来 $M$ 行表示 $M$ 条指令，每条指令的格式如题目描述所示。

输出格式

对于每个询问，输出一行一个整数，表示该询问的答案。

样例1输入

5 5
1 3 5 7 9
Q 1 5
C 1 5 1
Q 1 5
C 3 3 6
Q 2 4

样例1输出

1
2
4

数据范围

对于所有测试数据保证： $1 <= N,M <= 10^5$，修改过程中涉及的所有数值不超过64位有符号整数的范围。