package main

import (
	"bufio"
	"bytes"
	"io"
	"os"
	"strconv"
)

type SegTree struct {
	sum []int64
	mx  []int64
}

func NewSegTree(a []int64, n int) *SegTree {
	st := &SegTree{
		sum: make([]int64, 4*n+5),
		mx:  make([]int64, 4*n+5),
	}
	st.build(1, 1, n, a)
	return st
}

func (st *SegTree) build(p, l, r int, a []int64) {
	if l == r {
		st.sum[p] = a[l]
		st.mx[p] = a[l]
		return
	}
	m := (l + r) >> 1
	st.build(p<<1, l, m, a)
	st.build(p<<1|1, m+1, r, a)
	st.pull(p)
}

func (st *SegTree) pull(p int) {
	st.sum[p] = st.sum[p<<1] + st.sum[p<<1|1]
	if st.mx[p<<1] > st.mx[p<<1|1] {
		st.mx[p] = st.mx[p<<1]
	} else {
		st.mx[p] = st.mx[p<<1|1]
	}
}

func (st *SegTree) rangeMod(p, l, r, ql, qr int, x int64) {
	if st.mx[p] < x {
		return
	}
	if l == r {
		v := st.sum[p] % x
		st.sum[p] = v
		st.mx[p] = v
		return
	}
	m := (l + r) >> 1
	if ql <= m {
		st.rangeMod(p<<1, l, m, ql, qr, x)
	}
	if qr > m {
		st.rangeMod(p<<1|1, m+1, r, ql, qr, x)
	}
	st.pull(p)
}

func (st *SegTree) pointSet(p, l, r, idx int, v int64) {
	if l == r {
		st.sum[p] = v
		st.mx[p] = v
		return
	}
	m := (l + r) >> 1
	if idx <= m {
		st.pointSet(p<<1, l, m, idx, v)
	} else {
		st.pointSet(p<<1|1, m+1, r, idx, v)
	}
	st.pull(p)
}

func (st *SegTree) rangeSum(p, l, r, ql, qr int) int64 {
	if ql <= l && r <= qr {
		return st.sum[p]
	}
	m := (l + r) >> 1
	var res int64
	if ql <= m {
		res += st.rangeSum(p<<1, l, m, ql, qr)
	}
	if qr > m {
		res += st.rangeSum(p<<1|1, m+1, r, ql, qr)
	}
	return res
}

var data []byte
var ptr int
var ndata int

func nextInt64() int64 {
	for ptr < ndata && data[ptr] <= ' ' {
		ptr++
	}
	var v int64
	for ptr < ndata && data[ptr] > ' ' {
		v = v*10 + int64(data[ptr]-'0')
		ptr++
	}
	return v
}

func main() {
	data, _ = io.ReadAll(bufio.NewReaderSize(os.Stdin, 1<<20))
	ndata = len(data)

	n := int(nextInt64())
	m := int(nextInt64())

	a := make([]int64, n+1)
	for i := 1; i <= n; i++ {
		a[i] = nextInt64()
	}

	st := NewSegTree(a, n)
	var out bytes.Buffer

	for i := 0; i < m; i++ {
		t := int(nextInt64())
		if t == 1 {
			l := int(nextInt64())
			r := int(nextInt64())
			out.WriteString(strconv.FormatInt(st.rangeSum(1, 1, n, l, r), 10))
			out.WriteByte('\n')
		} else if t == 2 {
			l := int(nextInt64())
			r := int(nextInt64())
			x := nextInt64()
			st.rangeMod(1, 1, n, l, r, x)
		} else {
			k := int(nextInt64())
			x := nextInt64()
			st.pointSet(1, 1, n, k, x)
		}
	}

	w := bufio.NewWriterSize(os.Stdout, 1<<20)
	w.Write(out.Bytes())
	w.Flush()
}