题目描述

给定一个长度为 $\red N$ 的数列 $\red A$，以及 $\red M$ 条指令，每条指令可能是以下两种之一：

$\red 1$、“C l r d”，表示把 $\red{A[l]}$ , $\red{A[l+1]}$ , $\red{......}$ , $\red{A[r]}$ 都加上 $\red d$。

$\red 2$、“Q l r”，表示询问 $\red{A[l]}$ , $\red{A[l+1]}$ , $\red{......}$ , $\red{A[r]}$ 的最大公约数(GCD)。

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

输入格式

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

第二行 $\red N$ 个整数 $\red{A[i]}$。

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

输出格式

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

每个答案占一行。

样例

输入样例

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
2
4

提示

$\red{N\le 500000}$,

$\red{M\le 100000}$