#include <bits/stdc++.h>
using namespace std;
int n, m;
long long a[200000 + 5];
long long f[200000 + 5];
long long sumf[200000 + 5];
void ini() {
  f[0] = f[1] = 1;
  for (int i = 2; i <= 200000; i++) {
    f[i] = (f[i - 1] + f[i - 2]) % 1000000000;
  }
  sumf[0] = 1;
  for (int i = 1; i <= 200000; i++) {
    sumf[i] = (sumf[i - 1] + f[i]) % 1000000000;
  }
}
struct node {
  int l;
  int r;
  long long s0;
  long long s1;
  int mark;
  int len() { return r - l + 1; }
} tree[200000 * 4 + 5];
inline long long fib(int n) { return n < 0 ? 0 : f[n]; }
inline long long get_s(int pos, int n) {
  return tree[pos].s0 * fib(n - 2) + tree[pos].s1 * fib(n - 1);
}
void push_up(int pos) {
  tree[pos].s0 =
      (tree[pos << 1].s0 + get_s(pos << 1 | 1, tree[pos << 1].len())) %
      1000000000;
  tree[pos].s1 =
      (tree[pos << 1].s1 + get_s(pos << 1 | 1, tree[pos << 1].len() + 1)) %
      1000000000;
}
void build(int l, int r, int pos) {
  tree[pos].l = l;
  tree[pos].r = r;
  if (l == r) {
    tree[pos].s0 = a[l] % 1000000000;
    tree[pos].s1 = a[l] % 1000000000;
    return;
  }
  int mid = (l + r) >> 1;
  build(l, mid, pos << 1);
  build(mid + 1, r, pos << 1 | 1);
  push_up(pos);
}
void push_down(int pos) {
  if (tree[pos].mark) {
    tree[pos << 1].mark = (tree[pos << 1].mark + tree[pos].mark) % 1000000000;
    tree[pos << 1 | 1].mark =
        (tree[pos << 1 | 1].mark + tree[pos].mark) % 1000000000;
    tree[pos << 1].s0 = (tree[pos << 1].s0 + sumf[tree[pos << 1].len() - 1] *
                                                 tree[pos].mark % 1000000000) %
                        1000000000;
    tree[pos << 1].s1 =
        (tree[pos << 1].s1 +
         (sumf[tree[pos << 1].len()] - sumf[0]) * tree[pos].mark % 1000000000) %
        1000000000;
    tree[pos << 1 | 1].s0 =
        (tree[pos << 1 | 1].s0 +
         sumf[tree[pos << 1 | 1].len() - 1] * tree[pos].mark % 1000000000) %
        1000000000;
    tree[pos << 1 | 1].s1 =
        (tree[pos << 1 | 1].s1 + (sumf[tree[pos << 1 | 1].len()] - sumf[0]) *
                                     tree[pos].mark % 1000000000) %
        1000000000;
    tree[pos].mark = 0;
  }
}
void update_add(int L, int R, long long v, int pos) {
  if (L <= tree[pos].l && R >= tree[pos].r) {
    tree[pos].mark = (tree[pos].mark + v) % 1000000000;
    tree[pos].s0 = (tree[pos].s0 + sumf[tree[pos].len() - 1] * v % 1000000000) %
                   1000000000;
    tree[pos].s1 =
        (tree[pos].s1 + (sumf[tree[pos].len()] - sumf[0]) * v % 1000000000) %
        1000000000;
    return;
  }
  push_down(pos);
  int mid = (tree[pos].l + tree[pos].r) >> 1;
  if (L <= mid) update_add(L, R, v, pos << 1);
  if (R > mid) update_add(L, R, v, pos << 1 | 1);
  push_up(pos);
}
void update_set(int upos, long long v, int pos) {
  if (tree[pos].l == tree[pos].r) {
    tree[pos].s0 = v % 1000000000;
    tree[pos].s1 = v % 1000000000;
    tree[pos].mark = 0;
    return;
  }
  push_down(pos);
  int mid = (tree[pos].l + tree[pos].r) >> 1;
  if (upos <= mid)
    update_set(upos, v, pos << 1);
  else
    update_set(upos, v, pos << 1 | 1);
  push_up(pos);
}
long long query(int L, int R, int pos) {
  if (L <= tree[pos].l && R >= tree[pos].r) {
    int len = tree[pos].l - L;
    if (len == 0)
      return tree[pos].s0;
    else
      return get_s(pos, len);
  }
  push_down(pos);
  int mid = (tree[pos].l + tree[pos].r) >> 1;
  long long ans = 0;
  if (L <= mid) ans = (ans + query(L, R, pos << 1)) % 1000000000;
  if (R > mid) ans = (ans + query(L, R, pos << 1 | 1)) % 1000000000;
  return ans;
}
int main() {
  int opt, x, v, l, r, d;
  scanf("%d %d", &n, &m);
  ini();
  for (int i = 1; i <= n; i++) {
    scanf("%I64d", &a[i]);
  }
  build(1, n, 1);
  for (int i = 1; i <= m; i++) {
    scanf("%d", &opt);
    if (opt == 1) {
      scanf("%d %d", &x, &v);
      update_set(x, v, 1);
    } else if (opt == 2) {
      scanf("%d %d", &l, &r);
      printf("%I64d\n", query(l, r, 1));
    } else {
      scanf("%d %d %d", &l, &r, &d);
      update_add(l, r, d, 1);
    }
  }
}
