# The Child and Sequence

## 题目描述

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,a,...,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 ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF438D/876beae330acc049f49836f16bfed34538663977.png). 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,a,...,a[n] (1<=a[i]<=10^{9})$ — initial value of array elements. Each of the next $m$ lines begins with a number $type$ ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF438D/30ecae3e73b4644470ddff9dcee5b218291a621f.png). - 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$ .