题目描述

有一个长度为 $n$ 的数列 $\{a_n\}$ 和 $m$ 次操作，操作内容如下：

1. 格式为 1 l r，表示求 $\sum \limits _{i=l}^{r} a_i$ 的值并输出。
2. 格式为 2 l r x，表示对区间 $[l,r]$ 内每个数取模，模数为 $x$。
3. 格式为 3 k x，表示将 $a_k$ 修改为 $x$。

$1 \le n,m \le 10^5$，$1\le l,r,k\le n$，$1\le x \le 10^9$。

输入格式

第一行两个正整数 $n,m$，分别表示数列长度和操作次数。

第二行给出长为 $n$ 的数列 $\{a_n\}$。

接下来 $m$ 行，每行表示一次操作。

输出格式

对于每个操作 $1$，输出答案，每行一个整数。答案可能大于 $2^{31}-1$。

输入输出样例 #1

输入 #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

输入 #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