#include <bits/stdc++.h>
#pragma GCC optimize(3, "Ofast", "inline")
#pragma GCC target("avx,avx2")
using namespace std;
template <class t>
inline t read(t &x) {
  char c = getchar();
  bool f = 0;
  x = 0;
  while (!isdigit(c)) f |= c == '-', c = getchar();
  while (isdigit(c)) x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
  if (f) x = -x;
  return x;
}
template <class t>
inline void write(t x) {
  if (x < 0)
    putchar('-'), write(-x);
  else {
    if (x > 9) write(x / 10);
    putchar('0' + x % 10);
  }
}
const int mod = 1e9, N = 2e5 + 5;
int tr0[N << 2], tr1[N << 2], tg[N << 2], n, m, f[N], sum[N];
int trans(int x, int len) {
  if (!len) return tr0[x];
  if (len == 1) return tr1[x];
  return (1ll * tr0[x] * f[len - 2] + 1ll * tr1[x] * f[len - 1]) % mod;
}
void pushup(int x, int l, int r) {
  int mid = l + r >> 1;
  tr0[x] = tr0[x << 1] + trans(x << 1 | 1, mid - l + 1);
  if (tr0[x] > mod) tr0[x] -= mod;
  tr1[x] = tr1[x << 1] + trans(x << 1 | 1, mid - l + 2);
  if (tr1[x] > mod) tr1[x] -= mod;
}
void build(int x, int l, int r) {
  if (l == r) {
    tr0[x] = read(tr1[x]);
    return;
  }
  int mid = l + r >> 1;
  build(x << 1, l, mid);
  build(x << 1 | 1, mid + 1, r);
  pushup(x, l, r);
}
void add(int x, int len, int v) {
  tg[x] += v;
  if (tg[x] > mod) tg[x] -= mod;
  tr0[x] = (tr0[x] + 1ll * sum[len - 1] * v) % mod;
  tr1[x] = (tr1[x] + 1ll * (sum[len] - 1 + mod) * v) % mod;
}
void pushdown(int x, int l, int r) {
  if (!tg[x]) return;
  int mid = l + r >> 1;
  add(x << 1, mid - l + 1, tg[x]);
  add(x << 1 | 1, r - mid, tg[x]);
  tg[x] = 0;
}
void mfy(int x, int l, int r, int p, int v) {
  if (l == r) {
    tr0[x] = tr1[x] = v;
    return;
  }
  pushdown(x, l, r);
  int mid = l + r >> 1;
  if (p <= mid)
    mfy(x << 1, l, mid, p, v);
  else
    mfy(x << 1 | 1, mid + 1, r, p, v);
  pushup(x, l, r);
}
void up(int x, int l, int r, int p, int q, int v) {
  if (p <= l && r <= q) {
    add(x, r - l + 1, v);
    return;
  }
  pushdown(x, l, r);
  int mid = l + r >> 1;
  if (p <= mid) up(x << 1, l, mid, p, q, v);
  if (q > mid) up(x << 1 | 1, mid + 1, r, p, q, v);
  pushup(x, l, r);
}
int que(int x, int l, int r, int p, int q) {
  if (p <= l && r <= q) return trans(x, l - p);
  pushdown(x, l, r);
  int mid = l + r >> 1, res = 0;
  if (p <= mid) res += que(x << 1, l, mid, p, q);
  if (q > mid) res += que(x << 1 | 1, mid + 1, r, p, q);
  if (res > mod) res -= mod;
  return res;
}
signed main() {
  read(n);
  read(m);
  f[0] = f[1] = 1;
  sum[0] = 1;
  sum[1] = 2;
  for (int i = 2; i <= n; i++) {
    f[i] = f[i - 1] + f[i - 2];
    if (f[i] > mod) f[i] -= mod;
    sum[i] = sum[i - 1] + f[i];
    if (sum[i] > mod) sum[i] -= mod;
  }
  build(1, 1, n);
  while (m--) {
    int op;
    read(op);
    if (op == 1) {
      int p, v;
      read(p);
      read(v);
      mfy(1, 1, n, p, v);
    }
    if (op == 2) {
      int l, r;
      read(l);
      read(r);
      write(que(1, 1, n, l, r));
      puts("");
    }
    if (op == 3) {
      int l, r, v;
      read(l);
      read(r);
      read(v);
      up(1, 1, n, l, r, v);
    }
  }
}
