#include <bits/stdc++.h>
using namespace std;
;
long long read() {
  int x = 0, f = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  return x * f;
}
const double eps = 1e-8;
const int mod = 1e9 + 7;
const int maxn = 3e5 + 5;
const int INF = 0x3f3f3f3f;
const long long INFLL = 0x3f3f3f3f3f3f3f3f;
long long Maxx[maxn << 2];
long long sum[maxn << 2];
int a[maxn];
void push_up(int rt) {
  Maxx[rt] = max(Maxx[rt << 1], Maxx[rt << 1 | 1]);
  sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];
}
void build(int l, int r, int rt) {
  if (l == r) {
    Maxx[rt] = a[l];
    sum[rt] = a[l];
    return;
  }
  int mid = (l + r) >> 1;
  build(l, mid, rt << 1);
  build(mid + 1, r, rt << 1 | 1);
  push_up(rt);
}
void update_mod(int L, int R, long long val, int l, int r, int rt) {
  if (val > Maxx[rt]) return;
  if (l == r) {
    sum[rt] %= val;
    Maxx[rt] = sum[rt];
    return;
  }
  int mid = (l + r) >> 1;
  if (L <= mid) update_mod(L, R, val, l, mid, rt << 1);
  if (R > mid) update_mod(L, R, val, mid + 1, r, rt << 1 | 1);
  push_up(rt);
}
void update_val(int pos, long long val, int l, int r, int rt) {
  if (l == r) {
    sum[rt] = Maxx[rt] = val;
    return;
  }
  int mid = (l + r) >> 1;
  if (pos <= mid)
    update_val(pos, val, l, mid, rt << 1);
  else
    update_val(pos, val, mid + 1, r, rt << 1 | 1);
  push_up(rt);
}
long long query(int L, int R, int l, int r, int rt) {
  if (L <= l && r <= R) {
    return sum[rt];
  }
  int mid = (l + r) >> 1;
  long long ans = 0;
  if (L <= mid) ans += query(L, R, l, mid, rt << 1);
  if (R > mid) ans += query(L, R, mid + 1, r, rt << 1 | 1);
  return ans;
}
int main() {
  int n, m;
  cin >> n >> m;
  for (int i = 1; i <= n; i++) a[i] = read();
  build(1, n, 1);
  while (m--) {
    int op;
    scanf("%d", &op);
    if (op == 1) {
      int l, r;
      scanf("%d%d", &l, &r);
      printf("%lld\n", query(l, r, 1, n, 1));
    } else if (op == 2) {
      int l, r;
      long long x;
      scanf("%d%d%lld", &l, &r, &x);
      update_mod(l, r, x, 1, n, 1);
    } else if (op == 3) {
      int k;
      long long x;
      scanf("%d%lld", &k, &x);
      update_val(k, x, 1, n, 1);
    }
  }
}
