#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200020;
const int MOD = 1000000000;
int add(int a, int b) { return a >= MOD - b ? a - MOD + b : a + b; }
int mul(int a, int b) {
  return a ? (b < MOD / a ? a * b : (long long)a * b % MOD) : 0;
}
int sub(int a, int b) { return a < b ? a - b + MOD : a - b; }
template <int MATRIX_MAXN = 2>
struct Matrix {
  int n;
  int mat[MATRIX_MAXN][MATRIX_MAXN];
  void initEyeMatrix() {
    n = 2;
    mat[0][0] = 1;
    mat[0][1] = 0;
    mat[1][0] = 0;
    mat[1][1] = 1;
  }
  void initFibMatrix() {
    n = 2;
    mat[0][0] = 0;
    mat[0][1] = 1;
    mat[1][0] = 1;
    mat[1][1] = 1;
  }
  Matrix operator*(const Matrix &rhs) const {
    Matrix res;
    res.n = n;
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
        res.mat[i][j] = 0;
        for (int k = 0; k < n; k++) {
          res.mat[i][j] = add(res.mat[i][j], mul(mat[i][k], rhs.mat[k][j]));
        }
      }
    }
    return res;
  }
};
int fibsum[MAXN], a[MAXN];
Matrix<> fibmat[MAXN];
void initFibsum() {
  fibsum[0] = fibsum[1] = 1;
  fibmat[0].initEyeMatrix();
  Matrix<> fmat;
  fmat.initFibMatrix();
  for (int i = (2); i < (MAXN); i++)
    fibsum[i] = add(fibsum[i - 1], fibsum[i - 2]);
  for (int i = (1); i < (MAXN); i++) {
    fibmat[i] = fibmat[i - 1] * fmat;
    fibsum[i] = add(fibsum[i - 1], fibsum[i]);
  }
}
int getFib(int n, int f0, int f1) {
  return add(mul(f0, fibmat[n].mat[0][0]), mul(f1, fibmat[n].mat[1][0]));
}
struct Segment {
  int f0, f1, delta, size;
  Segment(int f0 = 0, int f1 = 0, int delta = 0, int size = 0)
      : f0(f0), f1(f1), delta(delta), size(size) {}
  int getF0() const { return add(f0, mul(delta, fibsum[size - 1])); }
  int getF1() const { return add(f1, mul(delta, sub(fibsum[size], 1))); }
  Segment operator+(const Segment &rhs) const {
    return Segment(add(getF0(), getFib(size, rhs.getF0(), rhs.getF1())),
                   add(getF1(), getFib(size + 1, rhs.getF0(), rhs.getF1())), 0,
                   size + rhs.size);
  }
};
template <int MAXN = 200020, int MAXNODE = MAXN << 2>
struct SegmentTree {
  int n;
  Segment seg[MAXNODE];
  static int LEFT(int idx) { return idx << 1; }
  static int RIGHT(int idx) { return (idx << 1) | 1; }
  void _build(int idx, int lower, int upper) {
    if (lower == upper) {
      seg[idx] = Segment(a[lower], a[lower], 0, 1);
      return;
    }
    int middle = (lower + upper) >> 1;
    _build(LEFT(idx), lower, middle);
    _build(RIGHT(idx), middle + 1, upper);
    seg[idx] = seg[LEFT(idx)] + seg[RIGHT(idx)];
  }
  void init(int n) {
    this->n = n;
    _build(1, 0, n - 1);
  }
  void pushDown(int idx) {
    seg[LEFT(idx)].delta = add(seg[LEFT(idx)].delta, seg[idx].delta);
    seg[RIGHT(idx)].delta = add(seg[RIGHT(idx)].delta, seg[idx].delta);
    seg[idx].delta = 0;
  }
  int l, r, x, v;
  void _modify(int idx, int lower, int upper) {
    if (l <= lower && upper <= r) {
      seg[idx].delta = add(seg[idx].delta, v);
      return;
    }
    pushDown(idx);
    int middle = (lower + upper) >> 1;
    if (r <= middle) {
      _modify(LEFT(idx), lower, middle);
    } else if (middle < l) {
      _modify(RIGHT(idx), middle + 1, upper);
    } else {
      _modify(LEFT(idx), lower, middle);
      _modify(RIGHT(idx), middle + 1, upper);
    }
    seg[idx] = seg[LEFT(idx)] + seg[RIGHT(idx)];
  }
  void modify(int l, int r, int v) {
    this->l = l;
    this->r = r;
    this->v = v;
    _modify(1, 0, n - 1);
  }
  void _assign(int idx, int lower, int upper) {
    if (lower == upper) {
      seg[idx] = Segment(v, v, 0, 1);
      return;
    }
    pushDown(idx);
    int middle = (lower + upper) >> 1;
    if (x <= middle) {
      _assign(LEFT(idx), lower, middle);
    } else {
      _assign(RIGHT(idx), middle + 1, upper);
    }
    seg[idx] = seg[LEFT(idx)] + seg[RIGHT(idx)];
  }
  void assign(int x, int v) {
    this->x = x;
    this->v = v;
    _assign(1, 0, n - 1);
  }
  Segment _calc(int idx, int lower, int upper) {
    if (l <= lower && upper <= r) return seg[idx];
    pushDown(idx);
    int middle = (lower + upper) >> 1;
    Segment res;
    if (r <= middle) {
      res = _calc(LEFT(idx), lower, middle);
    } else if (middle < l) {
      res = _calc(RIGHT(idx), middle + 1, upper);
    } else {
      res = _calc(LEFT(idx), lower, middle) +
            _calc(RIGHT(idx), middle + 1, upper);
    }
    seg[idx] = seg[LEFT(idx)] + seg[RIGHT(idx)];
    return res;
  }
  Segment calc(int l, int r) {
    this->l = l;
    this->r = r;
    return _calc(1, 0, n - 1);
  }
};
int n, m;
SegmentTree<> smt;
int main() {
  initFibsum();
  scanf("%d%d", &n, &m);
  for (int i = (0); i < (n); i++) scanf("%d", &a[i]);
  smt.init(n);
  for (int _ = (0); _ < (m); _++) {
    int op;
    scanf("%d", &op);
    if (op == 1) {
      int x, v;
      scanf("%d%d", &x, &v);
      smt.assign(x - 1, v);
    } else if (op == 2) {
      int l, r;
      scanf("%d%d", &l, &r);
      printf("%d\n", smt.calc(l - 1, r - 1).getF0());
    } else {
      int l, r, d;
      scanf("%d%d%d", &l, &r, &d);
      smt.modify(l - 1, r - 1, d);
    }
  }
  return 0;
}
