说明

时间限制：5 Sec 内存限制：256 MB 输入文件：gcdmax.in 输出文件：gcdmax.out

给定长度为 $N$ 的数列 $A$，共 $Q$ 次操作，四种操作类型：

$1$ $l$ $r$ $x$ 区间赋值：将区间 $[l,r]$ 所有元素改为 $x$

$2$ $l$ $r$ $x$ 区间取 $\gcd$：对区间 $[l,r]$ 每个元素，令 $a_i = \gcd(a_i, x)$

$3$ $l$ $r$ 区间查询最大值，输出结果

$4$ $l$ $r$ 区间查询总和，输出结果

输入格式

第一行 $N,Q$。

第二行 $N$ 个整数 $a_1\dots a_N$。

后续 $Q$ 行，每行一条上述操作。

输出格式

每条 $3$、$4$ 操作单独输出一行对应答案。

样例

样例 1

5 11
1 6 8 7 3
3 1 5
4 1 5
2 1 5 6
3 1 5
4 2 4
1 1 5 10
3 1 4
4 3 5
2 3 4 3
3 2 3
4 4 5

8
25
6
9
10
30
10
11

样例说明：

初始数组：$[1,6,8,7,3]$。

1. 查询最大值：$8$

2. 总和：$1+6+8+7+3=25$

3. 全体与 $6$ 取 $\gcd$：$\gcd(1,6)=1,\gcd(6,6)=6,\gcd(8,6)=2,\gcd(7,6)=1,\gcd(3,6)=3$

   数组变为 $[1,6,2,1,3]$

4. 区间最大值：$6$

5. $[2,4]$ 和：$6+2+1=9$

6. 整体赋值 $10$：$[10,10,10,10,10]$

7. $[1,4]$ 最大值：$10$

8. $[3,5]$ 和：$10+10+10=30$

9. $[3,4]$ 与 $3$ 取 $\gcd$：$\gcd(10,3)=1$，数组 $[10,10,1,1,10]$

10. $[2,3]$ 最大值：$10$

11. $[4,5]$ 和：$1+10=11$

数据范围

对于 8% 的数据，$N,Q \le 1000$。

对于 28% 的数据，$N \le 10^5$，$Q \le 1000$。

对于 100% 的额数据，$1\le N,Q\le 10^5$，$1\le a_i,x \le 10^9$，保证至少存在一条 $3$ 或 $4$ 查询操作。