#include <bits/stdc++.h>
using namespace std;
int n, m, f[200005], s[200005], a[200005];
struct node {
  int s0, s1, lz;
} t[800005];
inline int read() {
  int x = 0, f = 1;
  char ch = getchar();
  for (; !isdigit(ch); ch = getchar())
    if (ch == '-') f = -1;
  for (; isdigit(ch); ch = getchar()) x = (x + (x << 2) << 1) + (ch ^ 48);
  return x * f;
}
inline void write(int x) {
  if (x < 0) putchar('\n'), x = -x;
  if (x > 9) write(x / 10);
  putchar(x % 10 ^ 48);
}
void psd(int i, int l, int r) {
  if (t[i].lz) {
    int mid = l + r >> 1, li = i << 1, ri = li | 1;
    t[li].s0 = (t[li].s0 + (long long)t[i].lz * s[mid - l]) % 1000000000,
    t[li].s1 =
        (t[li].s1 + (long long)t[i].lz * (s[mid - l + 1] - 1)) % 1000000000;
    t[ri].s0 = (t[ri].s0 + (long long)t[i].lz * s[r - mid - 1]) % 1000000000,
    t[ri].s1 = (t[ri].s1 + (long long)t[i].lz * (s[r - mid] - 1)) % 1000000000;
    t[li].lz = (t[li].lz + t[i].lz) % 1000000000,
    t[ri].lz = (t[ri].lz + t[i].lz) % 1000000000, t[i].lz = 0;
  }
}
void upd(int i, int l, int r) {
  int mid = l + r >> 1, li = i << 1, ri = li | 1;
  if (mid == l)
    t[i].s0 = (t[li].s0 + t[ri].s1) % 1000000000;
  else
    t[i].s0 = (t[li].s0 + (long long)t[ri].s0 * f[mid - l - 1] +
               (long long)t[ri].s1 * f[mid - l]) %
              1000000000;
  t[i].s1 = (t[li].s1 + (long long)t[ri].s0 * f[mid - l] +
             (long long)t[ri].s1 * f[mid - l + 1]) %
            1000000000;
}
void build(int i, int l, int r) {
  if (l == r) {
    t[i].s0 = t[i].s1 = a[l];
    return;
  }
  int mid = l + r >> 1;
  build(i << 1, l, mid), build(i << 1 | 1, mid + 1, r), upd(i, l, r);
}
void mdf(int i, int l, int r, int x, int y) {
  if (l == r) {
    t[i].s0 = t[i].s1 = y;
    return;
  }
  psd(i, l, r);
  int mid = l + r >> 1;
  if (x <= mid)
    mdf(i << 1, l, mid, x, y);
  else
    mdf(i << 1 | 1, mid + 1, r, x, y);
  upd(i, l, r);
}
int query(int i, int l, int r, int x, int y) {
  if (x <= l && y >= r) {
    if (x == l) return t[i].s0;
    if (x + 1 == l) return t[i].s1;
    return ((long long)t[i].s0 * f[l - x - 2] +
            (long long)t[i].s1 * f[l - x - 1]) %
           1000000000;
  }
  psd(i, l, r);
  int mid = l + r >> 1;
  if (y <= mid) return query(i << 1, l, mid, x, y);
  if (x > mid) return query(i << 1 | 1, mid + 1, r, x, y);
  return (query(i << 1, l, mid, x, y) + query(i << 1 | 1, mid + 1, r, x, y)) %
         1000000000;
}
void add(int i, int l, int r, int x, int y, int z) {
  if (x <= l && y >= r) {
    t[i].s0 = (t[i].s0 + (long long)z * s[r - l]) % 1000000000,
    t[i].s1 = (t[i].s1 + (long long)z * (s[r - l + 1] - 1)) % 1000000000,
    t[i].lz = (t[i].lz + z) % 1000000000;
    return;
  }
  psd(i, l, r);
  int mid = l + r >> 1;
  if (x <= mid) add(i << 1, l, mid, x, y, z);
  if (y > mid) add(i << 1 | 1, mid + 1, r, x, y, z);
  upd(i, l, r);
}
int main() {
  n = read(), m = read(), f[0] = f[1] = 1, s[0] = 1;
  for (int i = 2; i <= n; i++) f[i] = (f[i - 1] + f[i - 2]) % 1000000000;
  for (int i = 1; i <= n; i++)
    a[i] = read(), s[i] = (s[i - 1] + f[i]) % 1000000000;
  build(1, 1, n);
  while (m--) {
    int fl = read(), x = read(), y = read(), z;
    if (fl == 1) mdf(1, 1, n, x, y);
    if (fl == 2) write(query(1, 1, n, x, y)), putchar('\n');
    if (fl == 3) z = read(), add(1, 1, n, x, y, z);
  }
  return 0;
}
