```go
package main

import (
	"bufio"
	"fmt"
	"os"
)

const MOD int64 = 1000000000

type Node struct {
	s0, s1 int64
	lz0    int64
	lz1    int64
}

var (
	n, m int
	a    []int64
	f    []int64
	seg  []Node
)

func mod(x int64) int64 {
	x %= MOD
	if x < 0 {
		x += MOD
	}
	return x
}

func addMod(a, b int64) int64 {
	a += b
	if a >= MOD {
		a -= MOD
	}
	return a
}

func mulMod(a, b int64) int64 {
	return (a * b) % MOD
}

func G(A, B, k int64) (int64, int64) {
	// returns (G0,G1): G0=sum_{i=0}^{k-1} F_i*g_i, G1=sum_{i=0}^{k-1} F_{i+1}*g_i
	// where g_i = A*F_{i+1} + B*F_i
	// Derivations:
	// G0 = A*(F_k^2 - [k==0?0:1]) + B*(F_k*F_{k-1})
	// G1 = A*(F_k*F_{k+1}) + B*(F_k^2)
	if k <= 0 {
		return 0, 0
	}
	Fk := f[k]
	Fk1 := f[k+1]
	Fk_1 := f[k-1]
	Fk2 := mulMod(Fk, Fk)
	t := Fk2
	if k == 1 {
		t = mod(t - 1)
	} else {
		t = mod(t - 1)
	}
	// Actually for k>=1, sum_{i=0}^{k-1} F_i^2 = F_k*F_{k-1}
	// and sum_{i=0}^{k-1} F_i*F_{i+1} = F_k^2 - 1
	// so t = F_k^2 - 1 valid for k>=1
	G0 := addMod(mulMod(A, t), mulMod(B, mulMod(Fk, Fk_1)))
	G1 := addMod(mulMod(A, mulMod(Fk, Fk1)), mulMod(B, Fk2))
	return G0, G1
}

func apply(p, l, r int, d0, d1 int64) {
	if d0 == 0 && d1 == 0 {
		return
	}
	len := int64(r - l + 1)
	g0, g1 := G(d0, d1, len)
	seg[p].s0 = addMod(seg[p].s0, g0)
	seg[p].s1 = addMod(seg[p].s1, g1)
	seg[p].lz0 = addMod(seg[p].lz0, d0)
	seg[p].lz1 = addMod(seg[p].lz1, d1)
}

func push(p, l, r int) {
	d0, d1 := seg[p].lz0, seg[p].lz1
	if d0 == 0 && d1 == 0 {
		return
	}
	if l == r {
		seg[p].lz0, seg[p].lz1 = 0, 0
		return
	}
	mid := (l + r) >> 1
	left := p << 1
	right := left | 1
	apply(left, l, mid, d0, d1)
	shift := int64(mid - l + 1)
	nd0 := mod(mulMod(d0, f[shift-1]) + mulMod(d1, f[shift]))
	nd1 := mod(mulMod(d0, f[shift]) + mulMod(d1, f[shift+1]))
	apply(right, mid+1, r, nd0, nd1)
	seg[p].lz0, seg[p].lz1 = 0, 0
}

func pull(p int) {
	left := p << 1
	right := left | 1
	seg[p].s0 = addMod(seg[left].s0, seg[right].s0)
	seg[p].s1 = addMod(seg[left].s1, seg[right].s1)
}

func build(p, l, r int) {
	if l == r {
		val := mod(a[l])
		seg[p].s0 = val
		seg[p].s1 = val
		return
	}
	mid := (l + r) >> 1
	build(p<<1, l, mid)
	build(p<<1|1, mid+1, r)
	pull(p)
}

func rangeAdd(p, l, r, ql, qr int, d int64) {
	if ql <= l && r <= qr {
		offset := int64(l - ql)
		d0 := mod(mulMod(d, f[offset]))
		d1 := mod(mulMod(d, f[offset+1]))
		apply(p, l, r, d0, d1)
		return
	}
	push(p, l, r)
	mid := (l + r) >> 1
	if ql <= mid {
		rangeAdd(p<<1, l, mid, ql, qr, d)
	}
	if qr > mid {
		rangeAdd(p<<1|1, mid+1, r, ql, qr, d)
	}
	pull(p)
}

func pointQuery(p, l, r, idx int) int64 {
	if l == r {
		return seg[p].s0
	}
	push(p, l, r)
	mid := (l + r) >> 1
	if idx <= mid {
		return pointQuery(p<<1, l, mid, idx)
	}
	return pointQuery(p<<1|1, mid+1, r, idx)
}

func pointSet(p, l, r, idx int, v int64) {
	if l == r {
		val := mod(v)
		seg[p].s0 = val
		seg[p].s1 = val
		seg[p].lz0, seg[p].lz1 = 0, 0
		return
	}
	push(p, l, r)
	mid := (l + r) >> 1
	if idx <= mid {
		pointSet(p<<1, l, mid, idx, v)
	} else {
		pointSet(p<<1|1, mid+1, r, idx, v)
	}
	pull(p)
}

func rangeQuery(p, l, r, ql, qr int) (int64, int64) {
	if ql <= l && r <= qr {
		return seg[p].s0, seg[p].s1
	}
	push(p, l, r)
	mid := (l + r) >> 1
	if qr <= mid {
		return rangeQuery(p<<1, l, mid, ql, qr)
	}
	if ql > mid {
		return rangeQuery(p<<1|1, mid+1, r, ql, qr)
	}
	s0L, s1L := rangeQuery(p<<1, l, mid, ql, qr)
	s0R, s1R := rangeQuery(p<<1|1, mid+1, r, ql, qr)
	shift := int64(mid - max(l, ql) + 1)
	ns0R := mod(mulMod(s0R, f[shift-1]) + mulMod(s1R, f[shift]))
	ns1R := mod(mulMod(s0R, f[shift]) + mulMod(s1R, f[shift+1]))
	return addMod(s0L, ns0R), addMod(s1L, ns1R)
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func main() {
	in := bufio.NewReaderSize(os.Stdin, 1<<20)
	out := bufio.NewWriterSize(os.Stdout, 1<<20)
	defer out.Flush()

	fmt.Fscan(in, &n, &m)
	a = make([]int64, n+1)
	for i := 1; i <= n; i++ {
		fmt.Fscan(in, &a[i])
	}

	f = make([]int64, n+3)
	f[0] = 1
	f[1] = 1
	for i := 2; i < len(f); i++ {
		f[i] = mod(f[i-1] + f[i-2])
	}

	seg = make([]Node, 4*(n+5))
	build(1, 1, n)

	for ; m > 0; m-- {
		var t int
		fmt.Fscan(in, &t)
		if t == 1 {
			var x int
			var v int64
			fmt.Fscan(in, &x, &v)
			pointSet(1, 1, n, x, v)
		} else if t == 2 {
			var l, r int
			fmt.Fscan(in, &l, &r)
			s0, _ := rangeQuery(1, 1, n, l, r)
			fmt.Fprintln(out, mod(s0))
		} else {
			var l, r int
			var d int64
			fmt.Fscan(in, &l, &r, &d)
			rangeAdd(1, 1, n, l, r, mod(d))
		}
	}
}
```