当前没有测试数据。

2.取模问题

题目描述

给定一个长度为$n$的非负整数序列$a$，需要支持以下操作：

1. 给定$l$，$r$，输出$a[l]+a[l+1]+\cdots+a[r]$；
2. 给定$l$，$r$，$x$，将$a[l]$，$a[l+1]$，$\ldots$，$a[r]$对$x$取模；
3. 给定$k$，$y$，将$a[k]$修改为$y$。

输入格式

第一行两个整数$n$，$m$。

第二行$n$个整数$a[1]\ldots a[n]$。

接下来$m$行每行$3$或$4$个整数表示操作。

输出格式

对于每个操作$1$，输出一行一个整数表示答案。

数据范围与提示

• 对于$40\%$的数据，$n,m \leq 1000$；
• 对于$100\%$的数据，$n,m \leq 100000$，$1 \leq l,r,k \leq n$，$1 \leq x \leq 10^{9}$，$0 \leq a[i],y \leq 10^{9}$。

样例

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

8
5