#include <bits/stdc++.h>
using namespace std;
const int mod = 1000000000;
inline int add(int a, int b) {
  a += b;
  if (a >= mod) a -= mod;
  return a;
}
inline int mul(int a, int b) { return (a * (long long)b) % mod; }
int f1[201000];
int f2[201000];
int sf1[201000], sf2[201000];
int t1[600000], t2[600000];
int ta[600000];
inline void down(int np, int l, int r) {
  int m = (l + r) / 2;
  if (ta[np]) {
    t1[np * 2] = add(t1[np * 2], mul(ta[np], sf1[m - l + 1]));
    t2[np * 2] = add(t2[np * 2], mul(ta[np], sf2[m - l + 1]));
    t1[np * 2 + 1] = add(t1[np * 2 + 1], mul(ta[np], sf1[r - (m + 1) + 1]));
    t2[np * 2 + 1] = add(t2[np * 2 + 1], mul(ta[np], sf2[r - (m + 1) + 1]));
    ta[np * 2] += ta[np];
    ta[np * 2 + 1] += ta[np];
    ta[np] = 0;
  }
}
inline void merge(int& a, int a1, int a2, int& b, int b1, int b2, int x) {
  a = add(a1, add(mul(f1[x + 1], a2), mul(f1[x], b2)));
  b = add(b1, add(mul(f2[x + 1], a2), mul(f2[x], b2)));
}
inline void up(int np, int l, int r) {
  int m = (l + r) / 2;
  merge(t1[np], t1[np * 2], t1[np * 2 + 1], t2[np], t2[np * 2], t2[np * 2 + 1],
        m - l + 1);
}
inline void change(int np, int l, int r, int x, int c) {
  if (l == r) {
    t1[np] = 0;
    t2[np] = c;
    ta[np] = 0;
    return;
  }
  down(np, l, r);
  int m = (l + r) / 2;
  if (x <= m)
    change(np * 2, l, m, x, c);
  else
    change(np * 2 + 1, m + 1, r, x, c);
  up(np, l, r);
}
inline void addv(int np, int l, int r, int x, int y, int d) {
  if (x == l && y == r) {
    t1[np] = add(t1[np], mul(sf1[r - l + 1], d));
    t2[np] = add(t2[np], mul(sf2[r - l + 1], d));
    ta[np] += d;
    return;
  }
  down(np, l, r);
  int m = (l + r) / 2;
  if (x <= m && y > m) {
    addv(np * 2, l, m, x, m, d);
    addv(np * 2 + 1, m + 1, r, m + 1, y, d);
  } else if (x > m)
    addv(np * 2 + 1, m + 1, r, x, y, d);
  else
    addv(np * 2, l, m, x, y, d);
  up(np, l, r);
}
inline pair<int, int> query(int np, int l, int r, int x, int y) {
  if (x == l && y == r) return make_pair(t1[np], t2[np]);
  down(np, l, r);
  int m = (l + r) / 2;
  pair<int, int> p;
  if (x <= m && y > m) {
    pair<int, int> p1 = query(np * 2, l, m, x, m);
    pair<int, int> p2 = query(np * 2 + 1, m + 1, r, m + 1, y);
    merge(p.first, p1.first, p2.first, p.second, p1.second, p2.second,
          m - x + 1);
  } else if (x > m)
    p = query(np * 2 + 1, m + 1, r, x, y);
  else
    p = query(np * 2, l, m, x, y);
  up(np, l, r);
  return p;
}
int main() {
  int n, m;
  scanf("%d%d", &n, &m);
  f1[0] = 0;
  f1[1] = 1;
  for (int i = (2); i <= (200100); i++) f1[i] = add(f1[i - 1], f1[i - 2]);
  f2[0] = 1;
  f2[1] = 0;
  for (int i = (2); i <= (200100); i++) f2[i] = add(f2[i - 1], f2[i - 2]);
  sf1[0] = sf2[0] = 0;
  for (int i = (1); i <= (200101); i++) sf1[i] = add(sf1[i - 1], f1[i - 1]);
  for (int i = (1); i <= (200101); i++) sf2[i] = add(sf2[i - 1], f2[i - 1]);
  for (int i = 0; i < (n); i++) {
    int v;
    scanf("%d", &v);
    change(1, 0, n - 1, i, v);
  }
  while (m--) {
    int t;
    scanf("%d", &t);
    if (t == 1) {
      int x, v;
      scanf("%d%d", &x, &v);
      x--;
      change(1, 0, n - 1, x, v);
    } else if (t == 2) {
      int a, b;
      scanf("%d%d", &a, &b);
      a--;
      b--;
      pair<int, int> p = query(1, 0, n - 1, a, b);
      printf("%d\n", add(p.first, p.second));
    } else {
      int a, b, d;
      scanf("%d%d%d", &a, &b, &d);
      a--;
      b--;
      addv(1, 0, n - 1, a, b, d);
    }
  }
}
