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⁵). The second line contains n integers, separated by space: a[1], a[2], ..., a[n] (1 ≤ a[i] ≤ 10⁹) — 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⁹), 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⁹), 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.

5 5
1 2 3 4 5
2 3 5 4
3 3 5
1 2 5
2 1 3 3
1 1 3

8
5

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

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.

#include<cstdio>
#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
using namespace std;

#define ll long long

ll d[1000000],a[1000005],maxx[1000005];//区间值，原始值
ll n,q,mod;

void build(ll s, ll t, ll p) {

	if (s == t) {
	    maxx[p] = d[p] = a[s];
	    return;
	}

	ll m = s + ((t - s) >> 1);
	build(s, m, p * 2), build(m + 1, t, p * 2 + 1);
	d[p] = d[p * 2] + d[(p * 2) + 1];
	maxx[p]=max(maxx[p * 2],maxx[(p * 2) + 1]);
}

void update(ll l, ll c, ll s, ll t, ll p) {

	if (l == s && t == l) {
		d[p] = c;
		maxx[p] = c;
	    return;
	}

	ll m = s + ((t - s) >> 1);
	if (l <= m) update(l, c, s, m, p * 2);
	else update(l, c, m + 1, t, p * 2 + 1);
	d[p] = d[p * 2] + d[p * 2 + 1];
	maxx[p]=max(maxx[p * 2],maxx[(p * 2) + 1]);
}

void updatemo(int l,int r,int mod,int s,int t,int p)
{
    if(maxx[p] < mod) return;
    if(s == t)
    {
        d[p] %= mod;
        maxx[p] = d[p];
        return;
    }
    int m = s + ((t - s) >> 1);
    if (l <= m) updatemo(l, r, mod, s, m, p * 2);
    if (r > m) updatemo(l, r, mod, m + 1, t, p * 2 + 1);
    d[p] = d[p * 2] + d[(p * 2) + 1];
	maxx[p]=max(maxx[p * 2],maxx[(p * 2) + 1]);
}

ll getsum(ll l, ll r, ll s, ll t, ll p) {

	if (l <= s && t <= r) return d[p];

	ll m = s + ((t - s) >> 1);
	ll sum = 0;
	if (l <= m) sum += getsum(l, r, s, m, p * 2);
	if (r > m) sum += getsum(l, r, m + 1, t, p * 2 + 1);
	return sum;
}

int main()
{
	scanf("%lld%lld",&n,&q);
	for(int i=1;i<=n;i++){
		scanf("%lld",&a[i]);
	}
	build(1,n,1);
	ll op,x,y,mod;
	while (q--) {
		cin >> op;
	if (op == 1)
		cin >> x >> y,cout << getsum(x, y, 1, n, 1) <<endl;
	else if(op == 2)
		cin >> x >> y >> mod, updatemo(x, y, mod, 1, n, 1);
	else
		cin >> x >> y,update(x, y, 1, n, 1);
	}
}