#include <bits/stdc++.h>
using namespace std;
bool debug = false;
int n, m, k;
int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
long long ln, lk, lm;
const int mod = 1e9;
int a[200105];
long long f[200105], sf[200105];
long long s[1 << 20], s1[1 << 20], T[1 << 20];
long long gett(long long f1, long long f2, int cnt) {
  if (cnt == 1) return f1;
  if (cnt == 2) return f2;
  return (f2 * f[cnt - 1] % mod + f1 * f[cnt - 2] % mod) % mod;
}
void up(int rt, int l, int r) {
  int mid = (l + r) / 2;
  int lcnt = mid - l;
  (s[rt] = s[rt << 1] + gett(s[rt << 1 | 1], s1[rt << 1 | 1], lcnt + 1)) %= mod;
  (s1[rt] = s1[rt << 1] + gett(s[rt << 1 | 1], s1[rt << 1 | 1], lcnt + 2)) %=
      mod;
}
void build(int rt, int l, int r) {
  if (l >= r) return;
  if (l + 1 == r) {
    s[rt] = a[r];
    s1[rt] = a[r];
    return;
  }
  int mid = (l + r) / 2;
  build(rt << 1, l, mid);
  build(rt << 1 | 1, mid, r);
  up(rt, l, r);
}
void pdown(int rt, int l, int r) {
  if (T[rt] == 0) return;
  (s[rt] += sf[r - l] * T[rt] % mod) %= mod;
  (s1[rt] += (sf[r - l + 1] - 1 + mod) % mod * T[rt] % mod) %= mod;
  (T[rt << 1] += T[rt]) %= mod;
  (T[rt << 1 | 1] += T[rt]) %= mod;
  T[rt] = 0;
}
void update(int rt, int l, int r, int R) {
  pdown(rt, l, r);
  if (r < R || R <= l) return;
  if (l + 1 == r) {
    s[rt] = a[R];
    s1[rt] = a[R];
    return;
  }
  int mid = (l + r) / 2;
  update(rt << 1, l, mid, R);
  update(rt << 1 | 1, mid, r, R);
  up(rt, l, r);
}
long long query(int rt, int l, int r, int L, int R) {
  pdown(rt, l, r);
  if (r <= L || R <= l) return 0;
  if (L <= l && r <= R) {
    return gett(s[rt], s1[rt], l - L + 1);
  }
  int mid = (l + r) / 2;
  long long x = query(rt << 1, l, mid, L, R);
  long long y = query(rt << 1 | 1, mid, r, L, R);
  up(rt, l, r);
  return (x + y) % mod;
}
void init() {
  f[1] = 1;
  f[2] = 1;
  for (int i = 3; i <= n + 5; i++) f[i] = (f[i - 1] + f[i - 2]) % mod;
  for (int(i) = 1; (i) <= (int)(n); (i)++) sf[i] = (sf[i - 1] + f[i]) % mod;
  build(1, 0, n);
}
void upt(int rt, int l, int r, int L, int R, int v) {
  if (L <= l && r <= R) {
    (T[rt] += v) %= mod;
    pdown(rt, l, r);
    return;
  }
  int mid = (l + r) / 2;
  pdown(rt, l, r);
  if (r <= L || R <= l) return;
  upt(rt << 1, l, mid, L, R, v);
  upt(rt << 1 | 1, mid, r, L, R, v);
  up(rt, l, r);
}
int main() {
  scanf("%d%d", &n, &m);
  for (int(i) = 1; (i) <= (int)(n); (i)++) {
    scanf("%d", a + i);
  }
  init();
  int t, x, y, d;
  for (int(i) = 0; (i) < (int)(m); (i)++) {
    scanf("%d%d%d", &t, &x, &y);
    if (t == 1) {
      a[x] = y;
      update(1, 0, n, x);
    } else if (t == 2) {
      printf("%lld\n", query(1, 0, n, x - 1, y));
    } else {
      scanf("%d", &d);
      upt(1, 0, n, x - 1, y, d);
    }
  }
  return 0;
}
