六一儿童节,孩子来到皮克斯家,把家里弄得一团糟。皮克斯对他很生气。很多重要的东西都丢失了,特别是最喜欢的精选序列。
幸运的是,皮克斯记得如何修复序列。最初他应该创建一个整数数组 a[1], a[2], ..., a[n]。然后他应该执行一系列 m 操作。操作可以是以下操作之一:
1. 打印操作l, r。选择应该写下 $$\sum_{i=l}^{r}a[i]$$ 的值。
2. 模运算 l, r, x。 Picks 应该对每个 i (l ≤ i ≤ r) 执行赋值 a[i] = a[i] mod x。
3. 设置运算 k, x。 Picks 应该将 a[k] 的值设置为 x(换句话说,执行赋值 a[k] = x)。
你能帮助 Picks 执行整个操作序列吗?
输入
输入的第一行包含两个整数:n、m(1 ≤ n,m ≤ 105)。第二行包含 n 个整数,用空格分隔:a[1], a[2], ..., a[n] (1 ≤ a[i] ≤ 109) — 数组元素的初始值。
接下来的 m 行中的每一行都以数字类型 $$(type \in \{1,2,3\})$$ 开头。
- 如果 type = 1,则该行会多出两个整数:l, r (1 ≤ l ≤ r ≤ n),对应操作 1。
- 如果type = 2,则该行会多出三个整数:l, r, x (1 ≤ l ≤ r ≤ n; 1 ≤ x ≤ 109),对应操作2。
- 如果 type = 3,则该行会多出两个整数:k, x (1 ≤ k ≤ n; 1 ≤ x ≤ 109),对应操作 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。