#include <bits/stdc++.h>
using namespace std;
struct info {
  long long s, m;
  info(int x = 0) : s(x), m(x) {}
} T[3 * 100000 + 5];
info operator+(const info& x, const info& y) {
  info f;
  f.s = x.s + y.s;
  f.m = max(x.m, y.m);
  return f;
}
int n, m, i, x, y, t;
void build(int i, int x, int y) {
  int t = (x + y) / 2;
  if (x == y) {
    scanf("%d", &x);
    T[i] = info(x);
    return;
  }
  build(i * 2, x, t);
  build(i * 2 + 1, t + 1, y);
  T[i] = T[i * 2] + T[i * 2 + 1];
}
long long sum(int i, int x, int y, int a, int b) {
  int t = (x + y) / 2;
  if (b < x || y < a) return 0;
  if (x >= a && b >= y) return T[i].s;
  return sum(i * 2, x, t, a, b) + sum(i * 2 + 1, t + 1, y, a, b);
}
void ch(int i, int x, int y, int a, int b) {
  int t = (x + y) / 2;
  if (x == y) {
    T[i] = info(b);
    return;
  }
  if (a <= t)
    ch(i * 2, x, t, a, b);
  else
    ch(i * 2 + 1, t + 1, y, a, b);
  T[i] = T[i * 2] + T[i * 2 + 1];
}
void mod(int i, int x, int y, int a, int b, int k) {
  int t = (x + y) / 2;
  if (T[i].m < k) return;
  if (b < x || a > y) return;
  if (x == y) {
    T[i].m = T[i].s = T[i].s % k;
    return;
  }
  mod(i * 2, x, t, a, b, k);
  mod(i * 2 + 1, t + 1, y, a, b, k);
  T[i] = T[i * 2] + T[i * 2 + 1];
}
int main() {
  scanf("%d%d", &n, &m);
  build(1, 1, n);
  for (i = 1; i <= m; i++) {
    scanf("%d", &x);
    if (x == 1) {
      scanf("%d%d", &x, &y);
      printf("%I64d\n", sum(1, 1, n, x, y));
    } else if (x == 2) {
      scanf("%d%d%d", &x, &y, &t);
      mod(1, 1, n, x, y, t);
    } else {
      scanf("%d%d", &x, &y);
      ch(1, 1, n, x, y);
    }
  }
  return 0;
}
