Now Ave has become expert in these operations and tries to trick Alice. Ave gives an array to Alice of length n. Also, Ave asks q queries to Alice. The queries are of these types

1. Print the sum of the range from l to r.
2. Replace the numbers in the given range l to r with a[i] = a[i] % x
3. Replace the number at index m with x.

Help Alice to prove that humans are more intelligent than bots.

Input:
First line would contain two integers n, q.
Next line would contain n space-separated integers of the array.
Next q lines would contain option and their respective inputs.

Output:
If the operation is of type 1 then print the sum in the given range.

Constraints:

1 <= n, q <= 10⁵
1 <= array elements <= 10⁹
1 <= l <= r <= n
1 <= m <= n
1 <= x <= 10⁹