题目描述
给定一个长度为 $n$ 的非负整数序列 $a$，需要支持以下操作：
1. 给定 $l,r$,输出 $a[l]+a[l+1]+\cdots+a[r]$。
2. 给定 $l,r,x$，将 $a[l],a[l+1],\cdots,a[r]$ 对 $x$ 取模。
3. 给定 $k,y$,，将 $a[k]$ 修改为 $y$。
输入
第一行两个整数 $n,m$。
第二行 $n$ 个整数 $a[1]\cdots a[n]$。
接下来 $m$ 行每行 $3$ 或 $4$ 个整数表示操作。
输出
对于每个操作$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
提示
对于 $40\%$ 的数据，$n,m \leq 1000$。
对于 $100\%$ 的数据，$n,m \leq 10^5$，$1 \leq l,r,k \leq n$，$1 \leq x \leq 10^9$，$0 \leq a[i], y \leq 10^9$。