#include <bits/stdc++.h>
#pragma comment(linker, "/stack:102400000,102400000")
using namespace std;
int lowbit(int x) { return (x & -x); }
template <class T_>
T_ f_abs(T_ x) {
  return x < 0 ? -x : x;
}
template <class T_>
T_ f_max(T_ a, T_ b) {
  return a > b ? a : b;
}
template <class T_>
T_ f_min(T_ a, T_ b) {
  return a < b ? a : b;
}
template <class T_>
T_ gcd(T_ a, T_ b) {
  while (T_ t = a % b) a = b, b = t;
  return b;
}
template <class T_>
void f_swap(T_ &a, T_ &b) {
  T_ t = a;
  a = b;
  b = t;
}
const double eps = 1e-9;
const int dx[] = {-1, 1, 0, 0, -1, -1, 1, 1},
          dy[] = {0, 0, -1, 1, -1, 1, -1, 1};
const int inf = 0x7fffffff;
const int mod = 1000000007;
const int N = 100003;
int n, m, mx[N << 2];
long long sum[N << 2];
void Init() {}
void GetData() {}
void push_up(int root) {
  mx[root] = f_max(mx[(root << 1)], mx[(root << 1 | 1)]);
  sum[root] = sum[(root << 1)] + sum[(root << 1 | 1)];
}
void Build(int l, int r, int root) {
  if (l == r) {
    scanf("%d", &mx[root]);
    sum[root] = mx[root];
    return;
  }
  int mid = ((l + r) >> 1);
  Build(l, mid, (root << 1));
  Build(mid + 1, r, (root << 1 | 1));
  push_up(root);
}
long long Query(int L, int R, int l, int r, int root) {
  if (L <= l && r <= R) return sum[root];
  int mid = ((l + r) >> 1);
  long long res = 0;
  if (L <= mid) res += Query(L, R, l, mid, (root << 1));
  if (R > mid) res += Query(L, R, mid + 1, r, (root << 1 | 1));
  return res;
}
void ModUpdate(int L, int R, int md, int l, int r, int root) {
  if (mx[root] < md) return;
  if (l == r) {
    mx[root] %= md;
    sum[root] = mx[root];
    return;
  }
  int mid = ((l + r) >> 1);
  if (L <= mid) ModUpdate(L, R, md, l, mid, (root << 1));
  if (R > mid) ModUpdate(L, R, md, mid + 1, r, (root << 1 | 1));
  push_up(root);
}
void ToUpdate(int p, int x, int l, int r, int root) {
  if (l == r) {
    mx[root] = x;
    sum[root] = x;
    return;
  }
  int mid = ((l + r) >> 1);
  if (p <= mid) ToUpdate(p, x, l, mid, (root << 1));
  if (p > mid) ToUpdate(p, x, mid + 1, r, (root << 1 | 1));
  push_up(root);
}
void Solve() {
  int op, l, r, x;
  Build(1, n, 1);
  while (m--) {
    scanf("%d%d%d", &op, &l, &r);
    if (op == 1)
      printf("%I64d\n", Query(l, r, 1, n, 1));
    else if (op == 2) {
      scanf("%d", &x);
      ModUpdate(l, r, x, 1, n, 1);
    } else
      ToUpdate(l, r, 1, n, 1);
  }
}
int main() {
  while (~scanf("%d%d", &n, &m)) {
    Init();
    GetData();
    Solve();
  }
  return 0;
}
