D. 孩子与序列

每个测试的时间限制：$4$ 秒
每个测试的内存限制：$256$ MB
输入：标准输入
输出：标准输出

在儿童节那天，一个孩子来到了 Picks 的家，把他的房间弄得一团糟。Picks 非常生气。许多重要的东西都丢失了，尤其是 Picks 最喜欢的序列。

幸运的是，Picks 记得如何修复这个序列。首先，他需要创建一个整数数组 $a[1], a[2], \dots, a[n]$。然后，他需要依次执行 $m$ 个操作。每个操作可以是以下三种之一：

• 输出操作：给定 $l, r$，Picks 需要计算并输出 $\sum_{i=l}^{r} a[i]$ 的值。
• 取模操作：给定 $l, r, x$，Picks 需要对每个 $i$（$l \le i \le r$）执行赋值 $a[i] = a[i] \bmod x$。
• 赋值操作：给定 $k, x$，Picks 需要将 $a[k]$ 的值设为 $x$（即执行赋值 $a[k] = x$）。

你能帮助 Picks 完成这一系列操作吗？

输入

第一行包含两个整数 $n, m$（$1 \le n, m \le 10^5$）。
第二行包含 $n$ 个整数，以空格分隔：$a[1], a[2], \dots, a[n]$（$1 \le a[i] \le 10^9$）——数组元素的初始值。

接下来的 $m$ 行中，每行以一个整数 $type$ 开头：

• 如果 $type = 1$，则该行还有两个整数 $l, r$（$1 \le l \le r \le n$），对应操作 $1$。
• 如果 $type = 2$，则该行还有三个整数 $l, r, x$（$1 \le l \le r \le n$；$1 \le x \le 10^9$），对应操作 $2$。
• 如果 $type = 3$，则该行还有两个整数 $k, x$（$1 \le k \le n$；$1 \le x \le 10^9$），对应操作 $3$。

输出

对于每个操作 $1$，输出一行，包含对应的答案。注意答案可能超过 $32$ 位整数的范围。

示例

输入示例 1：

5 5
1 2 3 4 5
2 3 5 4
3 3 5
1 2 5
2 1 3 3
1 1 3

输出示例 1：

8
5

输入示例 2：

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

输出示例 2：

49
15
23
1
9

说明

考虑第一个测试用例：

• 初始时，$a = \{1, 2, 3, 4, 5\}$。
• 执行操作 $1$ 后，$a = \{1, 2, 3, 0, 1\}$。
• 执行操作 $2$ 后，$a = \{1, 2, 5, 0, 1\}$。
• 执行操作 $3$ 时，计算 $2 + 5 + 0 + 1 = 8$。
• 执行操作 $4$ 后，$a = \{1, 2, 2, 0, 1\}$。
• 执行操作 $5$ 时，计算 $1 + 2 + 2 = 5$。