#include <bits/stdc++.h>
using namespace std;
const int N = 1 << 19;
const int M = 1e9;
int f[N], a[N];
pair<int, int> p[N], s[N];
int dd[N];
void down(int u) {
  if (dd[u] != 0) {
    p[u + u].first = (p[u + u].first + 1LL * dd[u] * s[u + u].first % M) % M;
    p[u + u].second = (p[u + u].second + 1LL * dd[u] * s[u + u].second % M) % M;
    p[u + u + 1].first =
        (p[u + u + 1].first + 1LL * dd[u] * s[u + u + 1].first % M) % M;
    p[u + u + 1].second =
        (p[u + u + 1].second + 1LL * dd[u] * s[u + u + 1].second % M) % M;
    dd[u + u] = (dd[u] + dd[u + u]) % M;
    dd[u + u + 1] = (dd[u] + dd[u + u + 1]) % M;
    dd[u] = 0;
  }
}
void up(int u) {
  p[u] = make_pair((p[u + u].first + p[u + u + 1].first) % M,
                   (p[u + u].second + p[u + u + 1].second) % M);
  s[u] = make_pair((s[u + u].first + s[u + u + 1].first) % M,
                   (s[u + u].second + s[u + u + 1].second) % M);
}
void build(int u, int l, int r) {
  if (l == r) {
    p[u].first = 1LL * a[l] * f[l] % M;
    p[u].second = 1LL * a[l] * f[l - 1] % M;
    s[u].first = f[l];
    s[u].second = f[l - 1];
    return;
  }
  int md = l + r >> 1;
  build(u + u, l, md);
  build(u + u + 1, md + 1, r);
  up(u);
}
void update(int u, int l, int r, int cl, int cr, int v) {
  if (cl <= l && r <= cr) {
    p[u].first = (p[u].first + 1LL * v * s[u].first % M) % M;
    p[u].second = (p[u].second + 1LL * v * s[u].second % M) % M;
    dd[u] = (dd[u] + v) % M;
    return;
  }
  down(u);
  int md = l + r >> 1;
  if (cl <= md) update(u + u, l, md, cl, cr, v);
  if (md < cr) update(u + u + 1, md + 1, r, cl, cr, v);
  up(u);
}
pair<int, int> query(int u, int l, int r, int cl, int cr) {
  if (cl <= l && r <= cr) return p[u];
  down(u);
  pair<int, int> ret = pair<int, int>(0, 0), bet = pair<int, int>(0, 0),
                 ket = pair<int, int>(0, 0);
  int md = l + r >> 1;
  if (cl <= md) bet = query(u + u, l, md, cl, cr);
  if (md < cr) ket = query(u + u + 1, md + 1, r, cl, cr);
  ret.first = (ret.first + bet.first) % M;
  ret.second = (ret.second + bet.second) % M;
  ret.first = (ret.first + ket.first) % M;
  ret.second = (ret.second + ket.second) % M;
  up(u);
  return ret;
}
int bt[N];
void add(int id, int x) {
  for (; id < N; id += id & -id) bt[id] = (bt[id] + x) % M;
}
int get(int id) {
  int ret = 0;
  for (; id; id -= id & -id) ret = (ret + bt[id]) % M;
  return ret;
}
struct mat {
  int v[2][2];
  void init(int a, int b, int c, int d) {
    v[0][0] = a, v[0][1] = b, v[1][0] = c, v[1][1] = d;
  }
  mat operator*(mat &tmp) {
    mat res;
    res.init(0, 0, 0, 0);
    for (int i = 0; i < 2; ++i)
      for (int j = 0; j < 2; ++j)
        for (int k = 0; k < 2; ++k) {
          res.v[i][j] = (res.v[i][j] + 1LL * v[i][k] * tmp.v[k][j] % M) % M;
        }
    return res;
  }
  mat operator-(mat &tmp) {
    mat res;
    for (int i = 0; i < 2; ++i)
      for (int j = 0; j < 2; ++j) {
        res.v[i][j] = (v[i][j] - tmp.v[i][j] + M) % M;
      }
    return res;
  }
} lo;
mat pow(mat x, int y) {
  mat res;
  res.init(1, 0, 0, 1);
  for (; y; y >>= 1, x = x * x)
    if (y & 1) res = res * x;
  return res;
}
int main() {
  f[0] = f[1] = 1;
  for (int i = 2; i < N; i++) f[i] = (f[i - 1] + f[i - 2]) % M;
  int n, m;
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) {
    scanf("%d", a + i);
    add(i, a[i]), add(i + 1, M - a[i]);
  }
  build(1, 1, n);
  for (int i = 1; i <= m; i++) {
    int tp, u, v;
    scanf("%d%d%d", &tp, &u, &v);
    if (tp == 1) {
      int au = get(u), x = (v - au + M) % M;
      update(1, 1, n, u, u, x);
      add(u, x);
      add(u + 1, M - x);
    }
    if (tp == 2) {
      lo.init(0, 1, 1, M - 1);
      pair<int, int> ans = query(1, 1, n, u, v);
      int aa = 0, bb = 0;
      if (u > 1)
        lo = pow(lo, u - 1), aa = lo.v[1][0], bb = lo.v[1][1];
      else
        aa = 0, bb = 1;
      int www = (1LL * aa * ans.first % M + 1LL * bb * ans.second % M) % M;
      printf("%d\n", www);
    }
    if (tp == 3) {
      int d;
      scanf("%d", &d);
      update(1, 1, n, u, v, d);
      add(u, d), add(v + 1, M - d);
    }
  }
  return 0;
}
