#include <bits/stdc++.h>
using namespace std;
const int Maxn = 555555;
const long long INF = -1e18;
long long n, q, a[Maxn], sum[Maxn];
pair<long long, long long> mx[Maxn];
void updatemx(long long st, long long en, long long tag, long long pos,
              long long val) {
  if (st + 1 == en) {
    mx[tag].first = val, mx[tag].second = pos;
    return;
  }
  long long mid = (st + en) >> 1;
  if (pos < mid)
    updatemx(st, mid, tag * 2, pos, val);
  else
    updatemx(mid, en, tag * 2 + 1, pos, val);
  mx[tag] = max(mx[tag * 2], mx[tag * 2 + 1]);
}
pair<long long, long long> getmx(long long st, long long en, long long tag,
                                 long long lo, long long hi) {
  if (en <= lo || hi <= st) return make_pair(INF, (long long)0);
  if (lo <= st && en <= hi) return mx[tag];
  long long mid = (st + en) >> 1;
  return max(getmx(st, mid, tag * 2, lo, hi),
             getmx(mid, en, tag * 2 + 1, lo, hi));
}
void updatesum(long long st, long long en, long long tag, long long pos,
               long long val) {
  if (st + 1 == en) {
    sum[tag] = val;
    return;
  }
  long long mid = (st + en) >> 1;
  if (pos < mid)
    updatesum(st, mid, tag * 2, pos, val);
  else
    updatesum(mid, en, tag * 2 + 1, pos, val);
  sum[tag] = sum[tag * 2] + sum[tag * 2 + 1];
}
long long getsum(long long st, long long en, long long tag, long long lo,
                 long long hi) {
  if (en <= lo || hi <= st) return 0;
  if (lo <= st && en <= hi) return sum[tag];
  long long mid = (st + en) >> 1;
  return getsum(st, mid, tag * 2, lo, hi) +
         getsum(mid, en, tag * 2 + 1, lo, hi);
}
int main(int argc, char** argv) {
  cin >> n >> q;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    updatemx(1, n + 1, 1, i, a[i]);
    updatesum(1, n + 1, 1, i, a[i]);
  }
  for (int i = 1; i <= q; i++) {
    long long type;
    cin >> type;
    long long l, r, x, pos, val;
    pair<long long, long long> p;
    switch (type) {
      case (1):
        cin >> l >> r;
        cout << getsum(1, n + 1, 1, l, ++r) << endl;
        break;
      case (2):
        cin >> l >> r >> x;
        r++;
        p = getmx(1, n + 1, 1, l, r);
        while (p.first >= x) {
          updatemx(1, n + 1, 1, p.second, p.first % x);
          updatesum(1, n + 1, 1, p.second, p.first % x);
          p = getmx(1, n + 1, 1, l, r);
        }
        break;
      case (3):
        cin >> pos >> val;
        updatemx(1, n + 1, 1, pos, val);
        updatesum(1, n + 1, 1, pos, val);
        break;
    }
  }
  return 0;
}
