#include <bits/stdc++.h>
using namespace std;
int f[222222], sf[222222], s0[5 * 222222], s1[5 * 222222], n, m,
    add[5 * 222222];
inline int get(int s0, int s1, int x) {
  if (!x) return s0;
  if (x == 1) return s1;
  return ((1ll * f[x - 2] * s0) % 1000000000 +
          (1ll * f[x - 1] * s1) % 1000000000) %
         1000000000;
}
inline void recalc(int i, int l, int r) {
  int m = (l + r) / 2;
  s0[i] =
      (s0[i * 2] + get(s0[i * 2 + 1], s1[i * 2 + 1], m - l + 1)) % 1000000000;
  s1[i] =
      (s1[i * 2] + get(s0[i * 2 + 1], s1[i * 2 + 1], m - l + 2)) % 1000000000;
}
inline void push(int i, int l, int r) {
  if (!add[i]) return;
  if (l != r) add[i * 2] += add[i], add[i * 2] %= 1000000000;
  if (l != r) add[i * 2 + 1] += add[i], add[i * 2 + 1] %= 1000000000;
  int x = add[i];
  add[i] = 0;
  s0[i] = (s0[i] + 1ll * x * sf[r - l]) % 1000000000;
  int k = sf[r - l + 1] - 1;
  if (k < 0) k += 1000000000;
  s1[i] = (s1[i] + 1ll * x * k) % 1000000000;
}
inline void update(int l, int r, int p, int v, int i) {
  int m = (l + r) / 2;
  push(i, l, r);
  push(i * 2, l, m);
  push(i * 2 + 1, m + 1, r);
  if (l == r) {
    s0[i] = v;
    s1[i] = v;
    return;
  }
  if (m >= p)
    update(l, m, p, v, i * 2);
  else
    update(m + 1, r, p, v, i * 2 + 1);
  recalc(i, l, r);
}
inline int ask(int l, int r, int ll, int rr, int x, int i) {
  int m = (l + r) / 2;
  push(i, l, r);
  push(i * 2, l, m);
  push(i * 2 + 1, m + 1, r);
  if (l == ll && r == rr) {
    int res = get(s0[i], s1[i], x);
    return res;
  }
  int res = 0;
  if (m >= rr)
    res = ask(l, m, ll, rr, x, i * 2);
  else if (ll > m)
    res = ask(m + 1, r, ll, rr, x, i * 2 + 1);
  else {
    int r1 = ask(l, m, ll, m, x, i * 2);
    int r2 = ask(m + 1, r, m + 1, rr, x + (m - ll + 1), i * 2 + 1);
    res = (r1 + r2) % 1000000000;
  }
  return res;
}
inline void _add(int l, int r, int ll, int rr, int d, int i) {
  int m = (l + r) / 2;
  push(i, l, r);
  push(i * 2, l, m);
  push(i * 2 + 1, m + 1, r);
  if (l == ll && r == rr) {
    add[i] += d;
    push(i, l, r);
    return;
  }
  if (m >= rr)
    _add(l, m, ll, rr, d, i * 2);
  else if (ll > m)
    _add(m + 1, r, ll, rr, d, i * 2 + 1);
  else {
    _add(l, m, ll, m, d, i * 2);
    _add(m + 1, r, m + 1, rr, d, i * 2 + 1);
  }
  recalc(i, l, r);
}
inline void update(int p, int v) { update(1, n, p, v, 1); }
inline int ask(int l, int r) { return ask(1, n, l, r, 0, 1); }
inline void _add(int l, int r, int d) { _add(1, n, l, r, d, 1); }
int main() {
  scanf("%d%d", &n, &m);
  f[0] = f[1] = sf[0] = 1;
  sf[1] = 2;
  for (int i = 2; i <= n; i++) {
    f[i] = (f[i - 1] + f[i - 2]) % 1000000000;
    sf[i] = (sf[i - 1] + f[i]) % 1000000000;
  }
  for (int i = 1; i <= n; i++) {
    int x;
    scanf("%d", &x);
    update(i, x);
  }
  for (int i = 1; i <= m; i++) {
    int q;
    scanf("%d", &q);
    if (q == 1) {
      int p, v;
      scanf("%d%d", &p, &v);
      update(p, v);
    }
    if (q == 2) {
      int l, r;
      scanf("%d%d", &l, &r);
      int ans = ask(l, r);
      printf("%d\n", ans);
    }
    if (q == 3) {
      int l, r, d;
      scanf("%d%d%d", &l, &r, &d);
      _add(l, r, d);
    }
  }
  return 0;
}
