区间gcd II

题目描述

给定一个序列 $a_i$，维护两种操作：

• 1 l r x 给 $a[l \sim r]$ 加上 $x$。
• 2 l r 查询 $\gcd (a[l \sim r])$。

输入格式

第一行包含 $2$ 个整数 $n, m$，表示序列长度与操作次数。 第二行包含 $n$ 个整数 $a_i$，表示序列。 接下来 $m$ 行，每行包含一条上述指令。

数据范围

$n, m \le 10^5$ $a_i, x \le 10^9$

输出格式

对于每次查询，输出一个答案，占一行。

样例 #1

样例输入 #1

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

样例输出 #1

1
2
4