Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

D. The Child and Sequence

time limit per test

4 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputAt 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:

- Print operation
*l*,*r*. Picks should write down the value of . - Modulo operation
*l*,*r*,*x*. Picks should perform assignment*a*[*i*] =*a*[*i*]*mod**x*for each*i*(*l*≤*i*≤*r*). - 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?

Input

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.

Output

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

Examples

Input

5 5

1 2 3 4 5

2 3 5 4

3 3 5

1 2 5

2 1 3 3

1 1 3

Output

8

5

Input

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

Output

49

15

23

1

9

Note

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.

Codeforces (c) Copyright 2010-2017 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Mar/30/2017 05:43:16 (c3).

Desktop version, switch to mobile version.
User lists

Name |
---|