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?

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.

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$.