#include <bits/stdc++.h>
using namespace std;
const int maxn = (int)1e6;
const int mod = (int)1e9;
struct Tree {
  int S0, S1;
  int add, n;
  Tree() { S0 = S1 = add = 0; }
};
Tree T[maxn * 2];
int F[maxn];
int n, m;
int getF(int n, Tree v) {
  if (n == 0) return v.S0;
  if (n == 1) return v.S1;
  return ((1ll * F[n - 2] * v.S0) % mod + (1ll * F[n - 1] * v.S1) % mod) % mod;
}
void join(Tree &res, Tree &le, Tree &ri, int n) {
  res.S0 = (le.S0 + getF(n, ri)) % mod;
  res.S1 = (le.S1 + getF(n + 1, ri)) % mod;
}
void update(int v, int sl, int sr, int pos, int x) {
  if (!(sl <= pos && pos <= sr)) return;
  if (sl == sr) {
    T[v].S0 = T[v].S1 = x;
    return;
  }
  int mid = (sl + sr) >> 1;
  update(v + v, sl, mid, pos, x);
  update(v + v + 1, mid + 1, sr, pos, x);
  join(T[v], T[v + v], T[v + v + 1], mid - sl + 1);
}
pair<Tree, int> findSum(int v, int sl, int sr, int l, int r) {
  if (min(sr, r) - max(sl, l) < 0) return make_pair(Tree(), 0);
  if (l <= sl && sr <= r) {
    return make_pair(T[v], sr - sl + 1);
  }
  int mid = (sl + sr) >> 1;
  pair<Tree, int> le = findSum(v + v, sl, mid, l, r);
  pair<Tree, int> ri = findSum(v + v + 1, mid + 1, sr, l, r);
  pair<Tree, int> res;
  res.second = le.second + ri.second;
  join(res.first, le.first, ri.first, le.second);
  return res;
}
int main() {
  scanf("%d%d", &n, &m);
  F[0] = F[1] = 1;
  for (int i = 2; i <= n; ++i) F[i] = (F[i - 1] + F[i - 2]) % mod;
  for (int i = 1; i <= n; ++i) {
    int x;
    scanf("%d", &x);
    update(1, 1, n, i, x);
  }
  for (int it = 0; it < m; ++it) {
    int type;
    scanf("%d", &type);
    if (type == 1) {
      int v, x;
      scanf("%d%d", &v, &x);
      update(1, 1, n, v, x);
    } else if (type == 2) {
      int l, r;
      scanf("%d%d", &l, &r);
      Tree res = findSum(1, 1, n, l, r).first;
      printf("%d\n", res.S0);
    } else if (type == 3) {
      int l, r, d;
      scanf("%d%d%d", &l, &r, &d);
    }
  }
  return 0;
}
