#include <bits/stdc++.h>
using namespace std;
int n, qq;
int aint[530000][4][4], v[200010], fib[200010], fib2[200010];
int lazy[530000], sol[530000][4][4];
int mat[200010][4][4];
void inmult(int rez[4][4], int a[4][4], int b[4][4], int n1, int m1, int n2,
            int m2) {
  int aux[4][4];
  for (int i = 1; i <= n1; ++i)
    for (int j = 1; j <= m2; ++j) aux[i][j] = 0;
  for (int h = 1; h <= m1; ++h)
    for (int i = 1; i <= n1; ++i)
      for (int j = 1; j <= m2; ++j) {
        long long x = 1LL * a[i][h] * b[h][j];
        x %= 1000000000LL;
        aux[i][j] += x;
        aux[i][j] -= 1LL * ((1LL * aux[i][j]) >= 1000000000LL) * 1000000000LL;
      }
  for (int i = 1; i <= n1; ++i)
    for (int j = 1; j <= m2; ++j) rez[i][j] = aux[i][j];
}
void suma(int rez[4][4], int a[4][4], int b[4][4]) {
  int aux[4][4];
  for (int j = 1; j <= 2; ++j)
    aux[1][j] = a[1][j] + b[1][j],
    aux[1][j] -= 1LL * ((1LL * aux[1][j]) >= 1000000000LL) * 1000000000LL;
  for (int j = 1; j <= 2; ++j) rez[1][j] = aux[1][j];
}
void propag(int nod, int st, int dr) {
  if (!lazy[nod]) return;
  if (st != dr) {
    lazy[nod << 1] += lazy[nod];
    lazy[nod << 1] -=
        1LL * ((1LL * lazy[nod << 1]) >= 1000000000LL) * 1000000000LL;
    lazy[nod << 1 | 1] += lazy[nod];
    lazy[nod << 1 | 1] -=
        1LL * ((1LL * lazy[nod << 1 | 1]) >= 1000000000LL) * 1000000000LL;
  }
  int mama[4][4];
  long long x = 1LL * lazy[nod] * fib[dr - st + 1];
  long long y = 1LL * lazy[nod] * fib2[dr - st + 1];
  mama[1][1] = x % 1000000000LL;
  mama[1][2] = y % 1000000000LL;
  suma(aint[nod], aint[nod], mama);
  lazy[nod] = 0;
}
void build(int st, int dr, int nod) {
  if (st == dr) {
    aint[nod][1][1] = aint[nod][1][2] = v[st];
    return;
  }
  int mij = (st + dr) >> 1;
  build(st, mij, nod << 1);
  build(mij + 1, dr, nod << 1 | 1);
  int mama[4][4];
  inmult(mama, aint[nod << 1 | 1], mat[mij - st + 1], 1, 2, 2, 2);
  suma(aint[nod], aint[nod << 1], mama);
}
void update(int st, int dr, int x, int y, int val, int op, int nod) {
  propag(nod, st, dr);
  if (x <= st && dr <= y) {
    if (!op)
      aint[nod][1][1] = aint[nod][1][2] = val;
    else {
      lazy[nod] += val;
      lazy[nod] -= 1LL * ((1LL * lazy[nod]) >= 1000000000LL) * 1000000000LL;
      propag(nod, st, dr);
    }
    return;
  }
  int mij = (st + dr) >> 1;
  if (x <= mij)
    update(st, mij, x, y, val, op, nod << 1);
  else
    propag(nod << 1, st, mij);
  if (y > mij)
    update(mij + 1, dr, x, y, val, op, nod << 1 | 1);
  else
    propag(nod << 1 | 1, mij + 1, dr);
  int mama[4][4];
  inmult(mama, aint[nod << 1 | 1], mat[mij - st + 1], 1, 2, 2, 2);
  suma(aint[nod], aint[nod << 1], mama);
}
void query(int st, int dr, int x, int y, int nod) {
  propag(nod, st, dr);
  if (x <= st && dr <= y) {
    sol[nod][1][1] = aint[nod][1][1];
    sol[nod][1][2] = aint[nod][1][2];
    return;
  }
  int mij = (st + dr) >> 1;
  if (x <= mij) query(st, mij, x, y, nod << 1);
  if (y > mij) query(mij + 1, dr, x, y, nod << 1 | 1);
  int mama[4][4];
  if (x <= mij && y > mij) {
    inmult(mama, sol[nod << 1 | 1], mat[mij - max(x, st) + 1], 1, 2, 2, 2);
    suma(sol[nod], sol[nod << 1], mama);
  } else if (x <= mij)
    sol[nod][1][1] = sol[nod << 1][1][1], sol[nod][1][2] = sol[nod << 1][1][2];
  else
    sol[nod][1][1] = sol[nod << 1 | 1][1][1],
    sol[nod][1][2] = sol[nod << 1 | 1][1][2];
}
int main() {
  scanf("%d %d", &n, &qq);
  mat[0][1][1] = mat[0][2][2] = 1;
  fib[1] = fib[2] = 1;
  fib2[1] = 1, fib2[2] = 2;
  for (int i = 1; i <= n; ++i) {
    scanf("%d", &v[i]);
    mat[i][1][2] = mat[i][2][1] = mat[i][2][2] = 1;
    inmult(mat[i], mat[i - 1], mat[i], 2, 2, 2, 2);
    if (i > 2) {
      fib[i] = fib[i - 1] + fib[i - 2];
      fib2[i] = fib2[i - 1] + fib2[i - 2];
      fib[i] -= 1LL * ((1LL * fib[i]) >= 1000000000LL) * 1000000000LL;
      fib2[i] -= 1LL * ((1LL * fib2[i]) >= 1000000000LL) * 1000000000LL;
    }
  }
  for (int i = 1; i <= n; ++i) {
    fib[i] += fib[i - 1];
    fib2[i] += fib2[i - 1];
    fib[i] -= 1LL * ((1LL * fib[i]) >= 1000000000LL) * 1000000000LL;
    fib2[i] -= 1LL * ((1LL * fib2[i]) >= 1000000000LL) * 1000000000LL;
  }
  build(1, n, 1);
  for (; qq; --qq) {
    int op, x, y, hm;
    scanf("%d %d %d", &op, &x, &y);
    if (op == 3) scanf("%d", &hm);
    if (op == 1)
      update(1, n, x, x, y, 0, 1);
    else if (op == 2) {
      query(1, n, x, y, 1);
      printf("%d\n", sol[1][1][1]);
    } else
      update(1, n, x, y, hm, 1, 1);
  }
  return 0;
}
