#include <bits/stdc++.h>
using namespace std;
int mk, n, m, base[200010];
int val[200010 << 1];
long long s[200010 << 1];
int Max(int a, int b) { return a > b ? a : b; }
void build(int rt, int l, int r) {
  if (l == r) return val[rt] = s[rt] = base[l], void();
  int mid = (l + r) >> 1;
  build(rt << 1, l, mid);
  build(rt << 1 | 1, mid + 1, r);
  s[rt] = s[rt << 1] + s[rt << 1 | 1];
  val[rt] = Max(val[rt << 1], val[rt << 1 | 1]);
}
void _change(int rt, int l, int r, int p, int v) {
  if (l == r) return val[rt] = s[rt] = v, void();
  int mid = (l + r) >> 1;
  if (p <= mid)
    _change(rt << 1, l, mid, p, v);
  else
    _change(rt << 1 | 1, mid + 1, r, p, v);
  s[rt] = s[rt << 1] + s[rt << 1 | 1];
  val[rt] = Max(val[rt << 1], val[rt << 1 | 1]);
}
void update(int rt, int l, int r, int ul, int ur, int mod) {
  if (l == r) return val[rt] %= mod, s[rt] %= mod, void();
  int mid = (l + r) >> 1;
  if (ul <= mid && val[rt << 1] >= mod) update(rt << 1, l, mid, ul, ur, mod);
  if (ur > mid && val[rt << 1 | 1] >= mod)
    update(rt << 1 | 1, mid + 1, r, ul, ur, mod);
  s[rt] = s[rt << 1] + s[rt << 1 | 1];
  val[rt] = Max(val[rt << 1], val[rt << 1 | 1]);
}
long long query(int rt, int l, int r, int ql, int qr) {
  int mid = (l + r) >> 1;
  long long res = 0;
  if (l >= ql && r <= qr) return s[rt];
  if (ql <= mid) res += query(rt << 1, l, mid, ql, qr);
  if (qr > mid) res += query(rt << 1 | 1, mid + 1, r, ql, qr);
  return res;
}
int main() {
  cin >> n >> m;
  int l, r, v;
  for (int i = 1; i <= n; ++i) scanf("%d", &base[i]);
  build(1, 1, n);
  while (m--) {
    scanf("%d", &mk);
    if (mk == 1)
      scanf("%d%d", &l, &r), printf("%lld\n", query(1, 1, n, l, r));
    else if (mk == 2)
      scanf("%d%d%d", &l, &r, &v), update(1, 1, n, l, r, v);
    else
      scanf("%d%d", &r, &v), _change(1, 1, n, r, v);
  }
}
