### 问题描述 Komorebi 玩了很久叠硬币的游戏，现在他又想到了一种硬币的新玩法。 他买来 $n$ 个杯子，将它们一字排开放在桌面上（他的桌子就是那么大，别管了），编号从左到右分别是 $1,2,…,n$。一开始他在每个杯子中都放入了若干枚硬币。然后他每次会随机指定两个杯子，将这两个杯子之间的所有杯子（也包括这两个杯子，下同）中都放入 $k$ 个硬币（他就是那么有钱，别管了）。或者他会指定两个杯子，问自己这两个杯子之间的所有杯子一共放了几个硬币。 玩了一阵之后，由于惊人的记忆能力和心算能力，Komorebi 每次都答对了。于是他加大了游戏难度，换了一种问法：指定两个杯子，这两个杯子之间的每个杯子中放入的硬币数，它们的最大公约数是多少？ 尽管 Komorebi 很擅长数论，但是因为杯子太多，他也算不过来了，请你帮帮他吧！ ### 输入格式 输入第 $1$ 行包含两个正整数 $n$和 $q$，表示 Komorebi 一共有 $n$ 个杯子，且玩了 $q$ 轮游戏。 输入第 $2$ 行包含n个整数 $a_i$，表示编号为 $i$ 的杯子中一开始有 $a_i$ 个金币。 第 $3\sim q+2$ 行每行输入一条命令。命令有三种格式： 操作 $1$：`0 i j k`：$i$ 和 $j$ 都是正整数，表示 Komorebi 往编号为 $i$ 和 $j$ 的杯子之间的每个杯子中（包括编号为 $i$ 和 $j$ 的杯子本身，下同）都放入了 $k$ 个硬币； 操作 $2$：`1 i j`：$i$ 和 $j$ 都是正整数，表示 Komorebi 想算出编号为 $i$ 和 $j$ 的杯子之间的所有杯子中一共放入了几个硬币。 操作 $3$：`2 i j`：$i$ 和 $j$ 都是正整数，表示 Komorebi 想算出编号为 $i$ 和 $j$ 的杯子之间的每个杯子中的硬币数的最大公约数。 ### 输出格式 对于每个操作 $2$ 和操作 $3$ ，输出一行该该操作所要求的答案。 ### 样例输入 ```text 5 10 1 2 3 4 5 1 2 4 2 2 4 0 1 1 1 0 3 3 1 2 2 4 1 1 4 2 1 5 0 5 5 1 2 1 5 1 1 5 ``` ### 样例输出 ```text 9 1 2 12 1 2 18 ``` ### 说明/提示 对于所有评测数据，$1\leq n\leq 10^5，1\leq a_i\leq 10^5，1\leq q\leq 10^5，1\leq k\leq 10^5$。