#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2 * 100000 + 20, L = 2, MOD = 1000000000;
const int AAA[2][2] = {{0, 1}, {1, 1}};
long long TMP[L][L];
struct Matrix {
  int num[L][L];
  inline Matrix() { memset(num, 0, sizeof(num)); }
  inline Matrix(int x) {
    memset(num, 0, sizeof(num));
    num[0][1] = x;
  }
  inline Matrix operator*(const Matrix &b) const {
    Matrix c;
    for (int i = 0; i < L; ++i)
      for (int j = 0; j < L; ++j) {
        TMP[i][j] = 0;
        for (int k = 0; k < L; ++k)
          TMP[i][j] += (long long)num[i][k] * b.num[k][j];
        c.num[i][j] = TMP[i][j] % MOD;
      }
    return c;
  }
  inline Matrix operator+(const Matrix &b) const {
    Matrix c;
    for (int i = 0; i < L; ++i)
      for (int j = 0; j < L; ++j) {
        c.num[i][j] = num[i][j] + b.num[i][j];
        if (c.num[i][j] > MOD) c.num[i][j] -= MOD;
      }
    return c;
  }
} A, I, p[MAXN], f[MAXN];
struct seg_tree {
  int l, r, add;
  Matrix S;
} t[MAXN * 4];
int n, m;
inline void Update(int x) {
  t[x].S = t[(x << 1)].S +
           t[((x << 1) + 1)].S * p[t[(x << 1)].r - t[(x << 1)].l + 1];
}
inline void Build(int x, int l, int r) {
  t[x].l = l, t[x].r = r;
  if (l == r) {
    scanf("%d", &t[x].S.num[0][1]);
    return;
  }
  int mid = (t[x].l + t[x].r) >> 1;
  Build((x << 1), l, mid), Build(((x << 1) + 1), mid + 1, r);
  Update(x);
}
void init() {
  cin >> n >> m;
  I.num[0][0] = I.num[1][1] = 1;
  memcpy(A.num, AAA, sizeof(AAA));
  f[0] = I;
  for (int i = 1; i <= n; ++i) f[i] = f[i - 1] * A + I;
  p[0] = I;
  for (int i = 1; i <= n; ++i) p[i] = p[i - 1] * A;
  Build(1, 1, n);
}
inline void Clean(int x) {
  if (!t[x].add) return;
  int u = t[x].add;
  t[x].add = 0;
  t[x].S = t[x].S + (Matrix)u * f[t[x].r - t[x].l];
  if (t[x].l == t[x].r) return;
  t[(x << 1)].add += u, t[((x << 1) + 1)].add += u;
}
inline void Renew(int x, int l, int r, int d) {
  Clean(x);
  if (t[x].l == l && t[x].r == r) {
    if (d < 0)
      t[x].S = -d - 1;
    else
      t[x].add += d;
    return;
  }
  int mid = (t[x].l + t[x].r) >> 1;
  if (r <= mid)
    Renew((x << 1), l, r, d);
  else if (l > mid)
    Renew(((x << 1) + 1), l, r, d);
  else
    Renew((x << 1), l, mid, d), Renew(((x << 1) + 1), mid + 1, r, d);
  Clean((x << 1)), Clean(((x << 1) + 1));
  Update(x);
}
inline Matrix Query(int x, int S, int l, int r) {
  Clean(x);
  if (t[x].l == l && t[x].r == r) {
    return t[x].S * p[l - S];
  }
  int mid = (t[x].l + t[x].r) >> 1;
  Matrix CC;
  if (r <= mid)
    CC = Query((x << 1), S, l, r);
  else if (l > mid)
    CC = Query(((x << 1) + 1), S, l, r);
  else
    CC = Query((x << 1), S, l, mid) + Query(((x << 1) + 1), S, mid + 1, r);
  Clean((x << 1)), Clean(((x << 1) + 1));
  Update(x);
  return CC;
}
void solve() {
  int t;
  for (int i = 1; i <= m; ++i) {
    scanf("%d", &t);
    int x, y, v;
    if (t == 1) scanf("%d%d", &x, &v), Renew(1, x, x, -v - 1);
    if (t == 2)
      scanf("%d%d", &x, &y), printf("%d\n", Query(1, x, x, y).num[0][1]);
    if (t == 3) scanf("%d%d%d", &x, &y, &v), Renew(1, x, y, v);
  }
}
int main() {
  init();
  solve();
  fclose(stdin);
  fclose(stdout);
  return 0;
}
