CF438D The Child and Sequence

有一个长度为 $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$。

第一行两个正整数 $n,m$，分别表示数列长度和操作次数。 第二行给出长为 $n$ 的数列 $\{a_n\}$。 接下来 $m$ 行，每行表示一次操作。

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

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