#include <bits/stdc++.h>
using namespace std;
void debug_out() { cerr << '\n'; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << H;
  debug_out(T...);
}
const long long MAXN = 1e5 + 10;
long long n, m, a, l, r, x, k, type, seg[2][MAXN << 2];
void SET(long long p, long long x, long long id = 1, long long second = 0,
         long long e = n) {
  if (e - second < 2) {
    seg[0][id] = seg[1][id] = x;
    return;
  }
  long long mid = (second + e) >> 1;
  if (p < mid)
    SET(p, x, id << 1, second, mid);
  else
    SET(p, x, id << 1 | 1, mid, e);
  seg[0][id] = seg[0][id << 1] + seg[0][id << 1 | 1],
  seg[1][id] = max(seg[1][id << 1], seg[1][id << 1 | 1]);
  return;
}
void update(long long l, long long r, long long x, long long id = 1,
            long long second = 0, long long e = n) {
  if (e <= l or r <= second or seg[1][id] < x) return;
  if (e - second < 2) {
    seg[0][id] %= x, seg[1][id] %= x;
    return;
  }
  long long mid = (second + e) >> 1;
  update(l, r, x, id << 1, second, mid), update(l, r, x, id << 1 | 1, mid, e);
  seg[0][id] = seg[0][id << 1] + seg[0][id << 1 | 1],
  seg[1][id] = max(seg[1][id << 1], seg[1][id << 1 | 1]);
  return;
}
long long get(long long l, long long r, long long id = 1, long long second = 0,
              long long e = n) {
  if (e <= l or r <= second) return 0;
  if (l <= second and e <= r) return seg[0][id];
  long long mid = (second + e) >> 1,
            left_child = get(l, r, id << 1, second, mid),
            right_child = get(l, r, id << 1 | 1, mid, e);
  return left_child + right_child;
}
int32_t main() {
  cin >> n >> m;
  for (long long i = 0; i < n; i++) cin >> a, SET(i, a);
  while (m--) {
    cin >> type, type--;
    if (!type)
      cin >> l >> r, l--, cout << get(l, r) << '\n';
    else if (--type)
      cin >> k >> x, k--, SET(k, x);
    else
      cin >> l >> r >> x, l--, update(l, r, x);
  }
  return 0;
}
