#include <bits/stdc++.h>
using namespace std;
void dbg(const char* fmt, ...) {}
const int MOD = int(1e9);
const int N = 3 * int(1e5);
long long __fib[N + 1];
long long* fib = __fib + 1;
long long sumFib[N];
void initFib() {
  fib[-1] = 0;
  fib[0] = fib[1] = 1;
  for (int i = 2; i < N; ++i) {
    fib[i] = fib[i - 2] + fib[i - 1];
    if (fib[i] >= MOD) fib[i] -= MOD;
  }
  sumFib[0] = fib[0];
  for (int i = 1; i < N; ++i) {
    sumFib[i] = sumFib[i - 1] + fib[i];
    if (sumFib[i] >= MOD) sumFib[i] -= MOD;
  }
}
struct FibSum {
 private:
  int sum0, sum1, cnt;

 public:
  FibSum() { sum0 = sum1 = cnt = 0; }
  FibSum(int x) {
    if (x <= -MOD || x >= MOD) x %= MOD;
    if (x < 0) x += MOD;
    sum0 = sum1 = x;
    cnt = 1;
  }
  int value() const { return sum0; }
  FibSum operator+(const FibSum& r) const {
    if (cnt == 0) return r;
    if (r.cnt == 0) return *this;
    FibSum res;
    res.sum0 =
        (int)((sum0 + fib[cnt - 2] * r.sum0 + fib[cnt - 1] * r.sum1) % MOD);
    res.sum1 = (int)((sum1 + fib[cnt - 1] * r.sum0 + fib[cnt] * r.sum1) % MOD);
    res.cnt = cnt + r.cnt;
    return res;
  }
  FibSum& operator+=(int d) {
    sum0 = (int)((sum0 + sumFib[cnt - 1] * d) % MOD);
    sum1 = (int)((sum1 + (sumFib[cnt] - fib[0] + MOD) * d) % MOD);
    return *this;
  }
  void print() const {
    dbg("(sum0 = %d, sum1 = %d, cnt = %d)\n", sum0, sum1, cnt);
  }
};
struct RangeTree {
 private:
  int kk;
  vector<FibSum> b;
  vector<int> _add;
  void update(int t) {
    dbg("update(%d) =", t);
    b[t] = b[2 * t] + b[2 * t + 1];
    b[t].print();
  }
  FibSum getSum(int t, int L, int R, int l, int r) {
    if (R < l || r < L) return FibSum();
    if (l <= L && R <= r) return b[t];
    pushModify(t);
    int M = (L + R) / 2;
    return getSum(2 * t, L, M, l, r) + getSum(2 * t + 1, M + 1, R, l, r);
  }
  void add(int t, int L, int R, int l, int r, int d) {
    if (R < l || r < L) return;
    if (l <= L && R <= r) {
      makeAdd(t, d);
      return;
    }
    pushModify(t);
    int M = (L + R) / 2;
    add(2 * t, L, M, l, r, d);
    add(2 * t + 1, M + 1, R, l, r, d);
    update(t);
  }
  void pushModify(int t) {
    if (_add[t] != 0) {
      makeAdd(2 * t, _add[t]);
      makeAdd(2 * t + 1, _add[t]);
      _add[t] = 0;
    }
  }
  void makeAdd(int t, int d) {
    dbg("makeAdd(%d %d) ", t, d);
    _add[t] += d;
    if (_add[t] >= MOD) _add[t] -= MOD;
    b[t] += d;
    b[t].print();
  }

 public:
  RangeTree(vector<int>& a) {
    int n = int(a.size());
    kk = 1;
    while (kk < n) kk *= 2;
    b.resize(kk * 2 + 10);
    _add.resize(kk * 2 + 10);
    for (int i = 0; i < n; ++i) b[i + kk] = FibSum(a[i]);
    for (int i = kk - 1; i >= 1; --i) {
      update(i);
    }
  }
  int getSum(int l, int r) {
    dbg("getSum(%d %d) = ", l, r);
    FibSum res = getSum(1, 0, kk - 1, l, r);
    res.print();
    return res.value();
  }
  void add(int l, int r, int d) {
    if (d <= -MOD || d >= MOD) d %= MOD;
    if (d < 0) d += MOD;
    dbg("add(%d %d %d)\n", l, r, d);
    add(1, 0, kk - 1, l, r, d);
  }
};
int main() {
  initFib();
  int n, m;
  scanf("%d%d", &n, &m);
  vector<int> a(n);
  for (int i = 0; i < n; ++i) scanf("%d", &a[i]);
  RangeTree tree(a);
  for (int i = 0; i < m; ++i) {
    int t;
    scanf("%d", &t);
    if (t == 1) {
      int x, v;
      scanf("%d%d", &x, &v);
      --x;
      int cur = tree.getSum(x, x);
      tree.add(x, x, v - cur);
    } else if (t == 2) {
      int l, r;
      scanf("%d%d", &l, &r);
      --l, --r;
      printf("%d\n", tree.getSum(l, r));
    } else if (t == 3) {
      int l, r, d;
      scanf("%d%d%d", &l, &r, &d);
      --l, --r;
      tree.add(l, r, d);
    }
  }
  return 0;
}
