#include <bits/stdc++.h>
using namespace std;
const long long maxn = 1e5 + 5;
long long n;
long long a[maxn];
struct Tree {
  struct Node {
    long long maxx;
    long long sum;
    inline Node operator=(const long long x) {
      this->maxx = this->sum = x;
      return *this;
    }
  } no[maxn << 2];
  inline void push_up(long long k) {
    no[k].maxx = max(no[(k << 1)].maxx, no[(k << 1 | 1)].maxx);
    no[k].sum = no[(k << 1)].sum + no[(k << 1 | 1)].sum;
  }
  inline void build_tree(long long l, long long r, long long k) {
    if (l == r) {
      no[k] = a[l];
      return;
    }
    long long mid = (l + r) >> 1;
    build_tree(l, mid, (k << 1));
    build_tree(mid + 1, r, (k << 1 | 1));
    push_up(k);
  }
  inline void change(long long l, long long r, long long k, long long K,
                     long long x) {
    if (l == r) {
      no[k] = x;
      return;
    }
    long long mid = (l + r) >> 1;
    if (K <= mid)
      change(l, mid, (k << 1), K, x);
    else
      change(mid + 1, r, (k << 1 | 1), K, x);
    push_up(k);
  }
  inline void change_mod(long long l, long long r, long long k, long long L,
                         long long R, long long x) {
    if (no[k].maxx < x) return;
    if (l == r) {
      no[k] = no[k].sum % x;
      return;
    }
    long long mid = (l + r) >> 1;
    if (L <= mid) change_mod(l, mid, (k << 1), L, R, x);
    if (R > mid) change_mod(mid + 1, r, (k << 1 | 1), L, R, x);
    push_up(k);
  }
  inline long long get_sum(long long l, long long r, long long k, long long L,
                           long long R) {
    if (L <= l && r <= R) return no[k].sum;
    long long ans = 0;
    long long mid = (l + r) >> 1;
    if (L <= mid) ans += get_sum(l, mid, (k << 1), L, R);
    if (R > mid) ans += get_sum(mid + 1, r, (k << 1 | 1), L, R);
    return ans;
  }
} tr;
signed main() {
  long long m;
  scanf("%lld%lld", &n, &m);
  for (long long i = 1; i <= n; ++i) scanf("%lld", &a[i]);
  tr.build_tree(1, n, 1);
  long long cmd, l, r, x;
  while (m--) {
    scanf("%lld", &cmd);
    switch (cmd) {
      case 1:
        scanf("%lld%lld", &l, &r);
        printf("%lld\n", tr.get_sum(1, n, 1, l, r));
        break;
      case 2:
        scanf("%lld%lld%lld", &l, &r, &x);
        tr.change_mod(1, n, 1, l, r, x);
        break;
      default:
        scanf("%lld%lld", &l, &x);
        tr.change(1, n, 1, l, x);
    }
  }
  return 0;
}
