#include <bits/stdc++.h>
using namespace std;
int a[100005];
pair<long long, int> st[400005];
pair<long long, int> merge(pair<long long, int> p1, pair<long long, int> p2) {
  if (a[p1.second] >= a[p2.second])
    return pair<long long, int>(p1.first + p2.first, p1.second);
  return pair<long long, int>(p1.first + p2.first, p2.second);
}
void update(int n, int s, int e, int idx) {
  if (s == e)
    st[n] = pair<long long, int>(a[idx], idx);
  else {
    int mid = (s + e) / 2;
    if (idx <= mid)
      update(n + n, s, mid, idx);
    else
      update(n + n + 1, mid + 1, e, idx);
    st[n] = merge(st[n + n], st[n + n + 1]);
  }
}
pair<long long, int> query(int n, int s, int e, int l, int r) {
  if (s > r || l > e) return pair<long long, int>(0, 0);
  if (l <= s && e <= r) return st[n];
  int mid = (s + e) / 2;
  return merge(query(n + n, s, mid, l, r), query(n + n + 1, mid + 1, e, l, r));
}
int main() {
  int n, m, t;
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
    update(1, 1, n, i);
  }
  for (int i = 1; i <= m; i++) {
    scanf("%d", &t);
    if (t == 1) {
      int l, r;
      scanf("%d%d", &l, &r);
      printf("%lld\n", query(1, 1, n, l, r).first);
    } else if (t == 2) {
      int l, r, x;
      scanf("%d%d%d", &l, &r, &x);
      while (1) {
        int idx = query(1, 1, n, l, r).second;
        if (a[idx] < x) break;
        a[idx] %= x;
        update(1, 1, n, idx);
      }
    } else {
      int k, x;
      scanf("%d%d", &k, &x);
      a[k] = x;
      update(1, 1, n, k);
    }
  }
}
