#include <bits/stdc++.h>
using namespace std;
const long long INF = 0x3f3f3f3f;
const long long MOD = 1e9;
const double PI = acos(-1.0);
struct Matr {
  long long matr[2][2];
  void Init() { memset(matr, 0, sizeof matr); }
} F[210000];
Matr Multi(Matr a, Matr b) {
  Matr res;
  res.Init();
  for (int i = 0; i < 2; ++i)
    for (int j = 0; j < 2; ++j)
      for (int k = 0; k < 2; ++k)
        res.matr[i][j] = (res.matr[i][j] + a.matr[i][k] * b.matr[k][j]) % MOD;
  return res;
}
Matr X;
long long Fib[201000];
long long a[200100];
struct Tree {
  long long A, B;
} tree[200010 * 4];
long long lazy[200010 * 4];
void Push_up(int l, int r, int rt) {
  int mid = (l + r) / 2;
  Matr tmp = F[mid - l + 1];
  tree[rt].A = tree[rt << 1].A + (tree[rt << 1 | 1].A * tmp.matr[0][0] % MOD) +
               (tree[rt << 1 | 1].B * tmp.matr[1][0] % MOD);
  tree[rt].A %= MOD;
  tree[rt].B = tree[rt << 1].B + (tree[rt << 1 | 1].A * tmp.matr[0][1] % MOD) +
               (tree[rt << 1 | 1].B * tmp.matr[1][1] % MOD);
  tree[rt].B %= MOD;
}
void Build(int l, int r, int rt) {
  lazy[rt] = 0;
  if (l == r) {
    tree[rt].A = a[l];
    tree[rt].B = 0;
    return;
  }
  int mid = (l + r) / 2;
  Build(l, mid, rt << 1);
  Build(mid + 1, r, (rt << 1) | 1);
  Push_up(l, r, rt);
}
void Push_down(int l, int r, int rt) {
  int mid = (l + r) / 2;
  if (lazy[rt]) {
    long long ret1 = (F[mid - l + 1 + 2 - 1].matr[0][0] - 1) * lazy[rt] % MOD;
    long long ret2 = (F[mid - l + 2 - 1].matr[0][0] - 1) * lazy[rt] % MOD;
    tree[rt << 1].A = (tree[rt << 1].A + ret1) % MOD;
    tree[rt << 1].B = (tree[rt << 1].B + ret2) % MOD;
    ret1 = (F[r - mid + 2 - 1].matr[0][0] - 1) * lazy[rt] % MOD;
    ret2 = (F[r - mid - 1 + 2 - 1].matr[0][0] - 1) * lazy[rt] % MOD;
    tree[rt << 1 | 1].A = (tree[rt << 1 | 1].A + ret1) % MOD;
    tree[rt << 1 | 1].B = (tree[rt << 1 | 1].B + ret2) % MOD;
    lazy[rt << 1] += lazy[rt];
    lazy[rt << 1] %= MOD;
    lazy[rt << 1 | 1] += lazy[rt];
    lazy[rt << 1 | 1] %= MOD;
    lazy[rt] = 0;
  }
}
void Update1(int L, int R, int l, int r, int rt, long long val) {
  if (L <= l && r <= R) {
    long long ret1 = (F[r - l + 1 + 2 - 1].matr[0][0] - 1) * val % MOD;
    long long ret2 = (F[r - l + 2 - 1].matr[0][0] - 1) * val % MOD;
    tree[rt].A = (tree[rt].A + ret1) % MOD;
    tree[rt].B = (tree[rt].B + ret2) % MOD;
    lazy[rt] += val;
    return;
  }
  Push_down(l, r, rt);
  int mid = (l + r) / 2;
  if (L <= mid) Update1(L, R, l, mid, rt << 1, val);
  if (R > mid) Update1(L, R, mid + 1, r, (rt << 1) | 1, val);
  Push_up(l, r, rt);
}
Tree Que(int L, int R, int l, int r, int rt) {
  if (L <= l && r <= R) {
    return tree[rt];
  }
  int mid = (l + r) / 2;
  Push_down(l, r, rt);
  Tree res1, res2, ans;
  if (L <= mid && R <= mid)
    return Que(L, R, l, mid, rt << 1);
  else if (L > mid && R > mid)
    return Que(L, R, mid + 1, r, (rt << 1) | 1);
  else {
    Matr tmp = F[mid - max(L, l) + 1];
    res1 = Que(L, R, l, mid, rt << 1);
    res2 = Que(L, R, mid + 1, r, (rt << 1) | 1);
    ans.A = res1.A + (res2.A * tmp.matr[0][0] % MOD) +
            (res2.B * tmp.matr[1][0] % MOD);
    ans.A %= MOD;
    ans.B = res1.B + (res2.A * tmp.matr[0][1] % MOD) +
            (res2.B * tmp.matr[1][1] % MOD);
    ans.B %= MOD;
    return ans;
  }
}
int main() {
  int n, m;
  X.matr[0][0] = 1;
  X.matr[1][0] = 1;
  X.matr[0][1] = 1;
  X.matr[1][1] = 0;
  F[1] = X;
  for (int i = 2; i <= 200000; ++i) F[i] = Multi(F[i - 1], X);
  while (cin >> n >> m) {
    for (int i = 1; i <= n; ++i) scanf("%lld", &a[i]);
    Build(1, n, 1);
    int t;
    int l, r;
    long long val;
    long long temp;
    Tree RES;
    while (m--) {
      scanf("%d", &t);
      if (t == 1) {
        scanf("%d%lld", &l, &val);
        RES = Que(l, l, 1, n, 1);
        temp = val - RES.A;
        Update1(l, l, 1, n, 1, temp);
      } else if (t == 2) {
        scanf("%d%d", &l, &r);
        RES = Que(l, r, 1, n, 1);
        printf("%lld\n", RES.A);
      } else {
        scanf("%d%d%lld", &l, &r, &val);
        Update1(l, r, 1, n, 1, val);
      }
    }
  }
}
