#include <bits/stdc++.h>
using namespace std;
const long long INF = 0x3f3f3f3f;
const long long mod = 1e9 + 7;
const long long MAXN = 2e5 + 10;
inline int read() {
  int x = 0, fh = 1;
  char ch = getchar();
  for (; !isdigit(ch); ch = getchar())
    if (ch == '-') fh = -1;
  for (; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ 48);
  return x * fh;
}
void F() {}
long long n, m;
long long arr[MAXN];
struct node {
  long long l, r;
  long long x, mo;
} t[MAXN << 2];
inline void push_up(long long o) {
  t[o].mo = max(t[o << 1].mo, t[o << 1 | 1].mo);
  t[o].x = t[o << 1 | 1].x + t[o << 1].x;
}
inline void build(long long l, long long r, long long o) {
  t[o].l = l, t[o].r = r;
  if (l == r) {
    t[o].x = t[o].mo = arr[l];
    return;
  }
  long long mid = (l + r) >> 1;
  build(l, mid, o << 1);
  build(mid + 1, r, o << 1 | 1);
  push_up(o);
}
inline void update(long long l, long long o, long long x) {
  if (l == t[o].l && t[o].l == t[o].r) {
    t[o].x = t[o].mo = x;
    return;
  }
  long long mid = (t[o].l + t[o].r) >> 1;
  if (l <= mid)
    update(l, o << 1, x);
  else if (l > mid)
    update(l, o << 1 | 1, x);
  push_up(o);
}
inline void modif(long long l, long long r, long long o, long long p) {
  if (t[o].mo < p) return;
  if (t[o].l == t[o].r) {
    t[o].x = t[o].mo = t[o].mo % p;
    return;
  }
  long long mid = (t[o].l + t[o].r) >> 1;
  if (r <= mid)
    modif(l, r, o << 1, p);
  else if (l > mid)
    modif(l, r, o << 1 | 1, p);
  else {
    modif(l, mid, o << 1, p);
    modif(mid + 1, r, o << 1 | 1, p);
  }
  push_up(o);
}
inline long long query(long long l, long long r, long long o) {
  if (t[o].l >= l && t[o].r <= r) return t[o].x;
  if (t[o].l > r || t[o].r < l) return 0;
  long long ans = 0;
  long long mid = (t[o].l + t[o].r) >> 1;
  if (r <= mid)
    ans += query(l, r, o << 1);
  else if (l > mid)
    ans += query(l, r, o << 1 | 1);
  else {
    ans += query(l, r, o << 1);
    ans += query(l, r, o << 1 | 1);
  }
  return ans;
}
int main() {
  F();
  n = read();
  m = read();
  for (long long i = 1; i <= n; ++i) arr[i] = read();
  build(1, n, 1);
  while (m--) {
    long long op, l, r, x;
    cin >> op;
    ;
    if (op == 1) {
      cin >> l >> r;
      cout << query(l, r, 1) << endl;
    }
    if (op == 2) {
      long long p;
      cin >> l >> r >> p;
      modif(l, r, 1, p);
    }
    if (op == 3) {
      cin >> l >> x;
      update(l, 1, x);
    }
  }
  return 0;
}
