#include <bits/stdc++.h>
using namespace std;
const int inf = ~0U >> 1;
const long long INF = ~0ULL >> 1;
template <class T>
inline void read(T &n) {
  char c;
  for (c = getchar(); !(c >= '0' && c <= '9'); c = getchar())
    ;
  n = c - '0';
  for (c = getchar(); c >= '0' && c <= '9'; c = getchar()) n = n * 10 + c - '0';
}
int Pow(int base, int n, int mo) {
  if (n == 0) return 1;
  if (n == 1) return base % mo;
  int tmp = Pow(base, n >> 1, mo);
  tmp = (long long)tmp * tmp % mo;
  if (n & 1) tmp = (long long)tmp * base % mo;
  return tmp;
}
const int mo = 1000000000;
const int maxn = 200100;
struct fib {
  int x, y;
  inline fib() {}
  inline fib(int _x, int _y) : x(_x), y(_y) {}
} f[maxn], s[maxn];
struct node {
  int l, r, sign;
  fib d;
} t[maxn * 5];
int a[maxn], n, m, ty, x, y, d;
inline fib operator+(const fib &a, const fib &b) {
  return fib((a.x + b.x) % mo, (a.y + b.y) % mo);
}
inline fib operator*(const fib &a, int d) {
  return fib((long long)a.x * d % mo, (long long)a.y * d % mo);
}
void upd(int p) {
  int l = p << 1, r = p << 1 | 1;
  t[p].d = t[l].d;
  int D = t[r].l - t[p].l;
  fib tmp = fib(
      ((long long)t[r].d.x * f[D].x + (long long)t[r].d.y * f[D + 1].x) % mo,
      ((long long)t[r].d.x * f[D].y + (long long)t[r].d.y * f[D + 1].y) % mo);
  t[p].d = t[p].d + tmp;
}
void build(int p, int l, int r) {
  t[p].l = l;
  t[p].r = r;
  if (l != r) {
    build(p << 1, l, l + r >> 1);
    build(p << 1 | 1, (l + r >> 1) + 1, r);
    upd(p);
  } else {
    t[p].d = fib(a[l], 0);
  }
}
void add(int p, int d) {
  t[p].d = t[p].d + s[t[p].r - t[p].l] * d;
  t[p].sign += d;
  t[p].sign %= mo;
}
void push(int p) {
  if (t[p].sign) {
    add(p << 1, t[p].sign);
    add((p << 1) + 1, t[p].sign);
    t[p].sign = 0;
  }
}
void modify(int p, int l, int r, int d) {
  if (t[p].l == l && t[p].r == r) {
    add(p, d);
    return;
  }
  push(p);
  int m = t[p].l + t[p].r >> 1;
  if (r <= m)
    modify(p << 1, l, r, d);
  else if (l > m)
    modify(p << 1 | 1, l, r, d);
  else
    modify(p << 1, l, m, d), modify(p << 1 | 1, m + 1, r, d);
  upd(p);
}
void modify(int p, int tar, int d) {
  if (t[p].l == t[p].r) {
    t[p].d = fib(d, 0);
    return;
  }
  push(p);
  int m = t[p].l + t[p].r >> 1;
  if (tar <= m)
    modify(p << 1, tar, d);
  else
    modify(p << 1 | 1, tar, d);
  upd(p);
}
fib query(int p, int l, int r) {
  if (t[p].l == l && t[p].r == r) return t[p].d;
  push(p);
  int m = t[p].l + t[p].r >> 1;
  if (r <= m)
    return query(p << 1, l, r);
  else if (l > m)
    return query(p << 1 | 1, l, r);
  else {
    fib ret = query(p << 1, l, m);
    fib res = query(p << 1 | 1, m + 1, r);
    int D = m + 1 - l;
    fib tmp =
        fib(((long long)res.x * f[D].x + (long long)res.y * f[D + 1].x) % mo,
            ((long long)res.x * f[D].y + (long long)res.y * f[D + 1].y) % mo);
    return ret + tmp;
  }
}
int main() {
  scanf("%d%d", &n, &m);
  for (int i = (1); i <= (n); ++i) scanf("%d", &a[i]);
  f[0] = fib(1, 0);
  f[1] = fib(0, 1);
  for (int i = (2); i <= (n); ++i) f[i] = f[i - 1] + f[i - 2];
  s[0] = f[0];
  for (int i = (1); i <= (n); ++i) s[i] = s[i - 1] + f[i];
  build(1, 1, n);
  while (m--) {
    scanf("%d", &ty);
    if (ty == 1) {
      scanf("%d%d", &x, &y);
      modify(1, x, y);
    } else if (ty == 3) {
      scanf("%d%d%d", &x, &y, &d);
      modify(1, x, y, d);
    } else {
      scanf("%d%d", &x, &y);
      fib ret = query(1, x, y);
      printf("%d\n", (ret.x + ret.y) % mo);
    }
  }
  return 0;
}
