#include <bits/stdc++.h>
using namespace std;
struct tree {
  int l, r;
  long long s[2];
  long long tag;
} tr[1600001];
int a[200001];
long long mod = 1000000000;
long long mat[200006][3][3];
long long f[200006];
long long sx[200006];
inline void power(int n) {
  mat[0][1][1] = 1;
  mat[0][1][2] = 0;
  mat[0][2][1] = 0;
  mat[0][2][2] = 1;
  mat[1][1][1] = 0;
  mat[1][1][2] = 1;
  mat[1][2][1] = 1;
  mat[1][2][2] = 1;
  int i, j, k;
  for (k = 2; k <= n + 5; k++)
    for (i = 1; i <= 2; i++)
      for (j = 1; j <= 2; j++)
        mat[k][i][j] = (mat[k - 1][i][1] * mat[1][1][j] % mod +
                        mat[k - 1][i][2] * mat[1][2][j] % mod) %
                       mod;
  f[1] = 1;
  f[2] = 1;
  sx[1] = 1;
  sx[2] = 2;
  for (k = 3; k <= n + 5; k++) {
    f[k] = (f[k - 1] + f[k - 2]) % mod;
    sx[k] = (sx[k - 1] + f[k]) % mod;
  }
}
inline void up(int p) {
  int len = tr[p * 2].r - tr[p * 2].l + 1;
  tr[p].s[0] =
      ((tr[p * 2].s[0] + mat[len][1][1] * tr[p * 2 + 1].s[0] % mod) % mod +
       mat[len][2][1] * tr[p * 2 + 1].s[1] % mod) %
      mod;
  tr[p].s[1] =
      ((tr[p * 2].s[1] + mat[len][1][2] * tr[p * 2 + 1].s[0] % mod) % mod +
       mat[len][2][2] * tr[p * 2 + 1].s[1] % mod) %
      mod;
}
inline void down(int p) {
  if (tr[p].tag == 0) return;
  int len = tr[p].r - tr[p].l + 1;
  int len1 = len - len / 2, len2 = len / 2;
  long long x = tr[p].tag;
  tr[p].tag = 0;
  tr[p * 2].s[0] = (tr[p * 2].s[0] + x * sx[len1] % mod) % mod;
  tr[p * 2].s[1] = (tr[p * 2].s[1] + x * (sx[len1 + 1] - 1) % mod) % mod;
  tr[p * 2].tag = (tr[p * 2].tag + x) % mod;
  tr[p * 2 + 1].s[0] = (tr[p * 2 + 1].s[0] + x * sx[len2] % mod) % mod;
  tr[p * 2 + 1].s[1] =
      (tr[p * 2 + 1].s[1] + x * (sx[len2 + 1] - 1) % mod) % mod;
  tr[p * 2 + 1].tag = (tr[p * 2 + 1].tag + x) % mod;
}
inline void build(int p, int l, int r) {
  tr[p].l = l;
  tr[p].r = r;
  if (l != r) {
    int mid = (l + r) / 2;
    build(p * 2, l, mid);
    build(p * 2 + 1, mid + 1, r);
    up(p);
  } else {
    tr[p].s[0] = a[l];
    tr[p].s[1] = a[l];
  }
}
inline void change(int p, int l, int r, int x) {
  if (l <= tr[p].l && tr[p].r <= r) {
    tr[p].s[0] = x;
    tr[p].s[1] = x;
  } else {
    down(p);
    int mid = (tr[p].l + tr[p].r) / 2;
    if (l <= mid) change(p * 2, l, r, x);
    if (r > mid) change(p * 2 + 1, l, r, x);
    up(p);
  }
}
inline void cover(int p, int l, int r, int x) {
  if (l <= tr[p].l && tr[p].r <= r) {
    int len = tr[p].r - tr[p].l + 1;
    tr[p].s[0] = (tr[p].s[0] + x * sx[len] % mod) % mod;
    tr[p].s[1] = (tr[p].s[1] + x * (sx[len + 1] - 1) % mod) % mod;
    tr[p].tag = (tr[p].tag + x) % mod;
  } else {
    down(p);
    int mid = (tr[p].l + tr[p].r) / 2;
    if (l <= mid) cover(p * 2, l, r, x);
    if (r > mid) cover(p * 2 + 1, l, r, x);
    up(p);
  }
}
tree nw;
inline tree ask(int p, int l, int r) {
  if (l <= tr[p].l && tr[p].r <= r)
    return tr[p];
  else {
    down(p);
    int mid = (tr[p].l + tr[p].r) / 2;
    tree ans1 = nw, ans2 = nw, ans = nw;
    bool flag1 = false, flag2 = false;
    if (l <= mid) {
      flag1 = true;
      ans1 = ask(p * 2, l, r);
    }
    if (r > mid) {
      flag2 = true;
      ans2 = ask(p * 2 + 1, l, r);
    }
    if (flag1) {
      if (flag2) {
        ans.l = ans1.l;
        ans.r = ans2.r;
        int len = ans1.r - ans1.l + 1;
        ans.s[0] = ((ans1.s[0] + mat[len][1][1] * ans2.s[0] % mod) % mod +
                    mat[len][2][1] * ans2.s[1] % mod) %
                   mod;
        ans.s[1] = ((ans1.s[1] + mat[len][1][2] * ans2.s[0] % mod) % mod +
                    mat[len][2][2] * ans2.s[1] % mod) %
                   mod;
      } else
        ans = ans1;
    } else
      ans = ans2;
    return ans;
  }
}
int main() {
  int n, m;
  scanf("%d%d", &n, &m);
  int i;
  for (i = 1; i <= n; i++) scanf("%d", &a[i]);
  power(n);
  build(1, 1, n);
  int x, s, t;
  for (i = 1; i <= m; i++) {
    scanf("%d", &x);
    if (x == 1) {
      scanf("%d%d", &s, &t);
      change(1, s, s, t);
    } else if (x == 2) {
      scanf("%d%d", &s, &t);
      printf("%lld\n", ask(1, s, t).s[0]);
    } else {
      scanf("%d%d%d", &s, &t, &x);
      cover(1, s, t, x);
    }
  }
  return 0;
}
