#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int n;
long long sum[3 * N], mx[3 * N];
void assign(int i, int x, int u = 1, int s = 0, int e = n - 1) {
  if (i < s or e < i) return;
  if (s == e) {
    sum[u] = mx[u] = x;
    return;
  }
  int v = 2 * u, w = 2 * u + 1, m = (s + e) / 2;
  assign(i, x, v, s, m);
  assign(i, x, w, m + 1, e);
  sum[u] = sum[v] + sum[w];
  mx[u] = max(mx[v], mx[w]);
}
void mod(int l, int r, long long x, int u = 1, int s = 0, int e = n - 1) {
  if (r < s or e < l or mx[u] < x) return;
  if (s == e) {
    mx[u] %= x;
    sum[u] = mx[u];
    return;
  }
  int v = 2 * u, w = 2 * u + 1, m = (s + e) / 2;
  mod(l, r, x, v, s, m);
  mod(l, r, x, w, m + 1, e);
  sum[u] = sum[v] + sum[w];
  mx[u] = max(mx[v], mx[w]);
}
long long rsum(int l, int r, int u = 1, int s = 0, int e = n - 1) {
  if (r < s or e < l) return 0;
  if (l <= s and e <= r) return sum[u];
  int v = 2 * u, w = 2 * u + 1, m = (s + e) / 2;
  return rsum(l, r, v, s, m) + rsum(l, r, w, m + 1, e);
}
int main() {
  ios::sync_with_stdio(0), cin.tie(0);
  cin >> n;
  int m;
  cin >> m;
  int a[n];
  for (int i = 0; i < n; ++i) {
    cin >> a[i];
  }
  for (int i = 0; i < n; ++i) {
    assign(i, a[i]);
  }
  while (m--) {
    int tp;
    cin >> tp;
    if (tp == 1) {
      int l, r;
      cin >> l >> r;
      l--, r--;
      cout << rsum(l, r) << "\n";
    } else if (tp == 2) {
      int l, r, x;
      cin >> l >> r >> x;
      l--, r--;
      mod(l, r, x);
    } else {
      int k, x;
      cin >> k >> x;
      k--;
      assign(k, x);
    }
  }
  return 0;
}
