The Child and Sequence

题意翻译

给定数列，区间查询和，区间取模，单点修改。 $n, m \leq 10^5$。

题目描述

At the children's day, the child came to Picks's house, and messed his house up. Picks was angry at him. A lot of important things were lost, in particular the favorite sequence of Picks. Fortunately, Picks remembers how to repair the sequence. Initially he should create an integer array $ a[1],a[2],...,a[n] $ . Then he should perform a sequence of $ m $ operations. An operation can be one of the following: 1. Print operation $ l,r $ . Picks should write down the value of . 2. Modulo operation $ l,r,x $ . Picks should perform assignment $ a[i]=a[i] mod x $ for each $ i $ $ (l<=i<=r) $ . 3. Set operation $ k,x $ . Picks should set the value of $ a[k] $ to $ x $ (in other words perform an assignment $ a[k]=x $ ). Can you help Picks to perform the whole sequence of operations?

输入输出格式

输入格式

The first line of input contains two integer: $ n,m $ $ (1<=n,m<=10^{5}) $ . The second line contains $ n $ integers, separated by space: $ a[1],a[2],...,a[n] (1<=a[i]<=10^{9}) $ — initial value of array elements. Each of the next $ m $ lines begins with a number $ type $ . - If $ type=1 $ , there will be two integers more in the line: $ l,r (1<=l<=r<=n) $ , which correspond the operation 1. - If $ type=2 $ , there will be three integers more in the line: $ l,r,x (1<=l<=r<=n; 1<=x<=10^{9}) $ , which correspond the operation 2. - If $ type=3 $ , there will be two integers more in the line: $ k,x (1<=k<=n; 1<=x<=10^{9}) $ , which correspond the operation 3.

输出格式

For each operation 1, please print a line containing the answer. Notice that the answer may exceed the 32-bit integer.

输入输出样例

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

说明

Consider the first testcase: - At first, $ a={1,2,3,4,5} $ . - After operation $ 1 $ , $ a={1,2,3,0,1} $ . - After operation $ 2 $ , $ a={1,2,5,0,1} $ . - At operation $ 3 $ , $ 2+5+0+1=8 $ . - After operation $ 4 $ , $ a={1,2,2,0,1} $ . - At operation $ 5 $ , $ 1+2+2=5 $ .