#include <bits/stdc++.h>
template <typename T>
void read(T& x) {
  x = 0;
  int flag = 1;
  char c = getchar();
  for (; !isdigit(c); c = getchar())
    if (c == '-') flag = -1;
  for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
  x *= flag;
}
using namespace std;
const int maxn = 200010, mod = 1e9;
int n, q, a[maxn], f[maxn], pref[maxn], tag[maxn << 2];
void upd(int& x, int y) {
  x += y;
  if (x >= mod) x -= mod;
}
struct Mat {
  int a[2][2];
  Mat() { memset(a, 0, sizeof(a)); }
  Mat operator+(const Mat& b) const {
    Mat res = b;
    for (int i = 0; i <= (int)1; i++)
      for (int j = 0; j <= (int)1; j++) upd(res.a[i][j], a[i][j]);
    return res;
  }
  Mat operator*(const Mat& b) const {
    Mat res;
    for (int k = 0; k <= (int)1; k++)
      for (int i = 0; i <= (int)1; i++)
        for (int j = 0; j <= (int)1; j++)
          upd(res.a[i][j], 1ll * a[i][k] * b.a[k][j] % mod);
    return res;
  }
  void print() { printf("%d %d\n", a[0][0], a[0][1]); }
} c[maxn], ans[maxn << 2];
void init() {
  f[0] = f[1] = 1;
  for (int i = 2; i <= (int)n; i++) f[i] = (f[i - 1] + f[i - 2]) % mod;
  pref[0] = 1;
  for (int i = 1; i <= (int)n; i++) pref[i] = (pref[i - 1] + f[i]) % mod;
  Mat tmp;
  tmp.a[0][1] = tmp.a[1][0] = tmp.a[1][1] = 1;
  c[0].a[0][0] = c[0].a[1][1] = 1;
  c[1] = tmp;
  for (int i = 2; i <= (int)n; i++) c[i] = c[i - 1] * tmp;
}
void merge(int p, int l, int r) {
  int mid = (l + r) >> 1, tmp = mid - l + 1;
  ans[p] = ans[p << 1] + (ans[p << 1 | 1] * c[tmp]);
}
void build(int p, int l, int r) {
  if (l == r) {
    ans[p].a[0][0] = ans[p].a[0][1] = a[l];
    return;
  }
  int mid = (l + r) >> 1;
  build(p << 1, l, mid), build(p << 1 | 1, mid + 1, r);
  merge(p, l, r);
}
void change(int p, int l, int r, int x) {
  upd(ans[p].a[0][0], 1ll * x * pref[r - l] % mod);
  upd(ans[p].a[0][1], 1ll * x * (pref[r - l + 1] - 1 + mod) % mod);
  upd(tag[p], x);
}
void push_down(int p, int l, int r) {
  int mid = (l + r) >> 1;
  change(p << 1, l, mid, tag[p]), change(p << 1 | 1, mid + 1, r, tag[p]);
  tag[p] = 0;
}
void update(int p, int l, int r, int x, int y) {
  if (l == r) {
    ans[p].a[0][0] = ans[p].a[0][1] = y;
    return;
  }
  if (tag[p]) push_down(p, l, r);
  int mid = (l + r) >> 1;
  x <= mid ? update(p << 1, l, mid, x, y)
           : update(p << 1 | 1, mid + 1, r, x, y);
  merge(p, l, r);
}
void modify(int p, int l, int r, int ql, int qr, int x) {
  if (ql <= l && r <= qr) {
    change(p, l, r, x);
    return;
  }
  if (tag[p]) push_down(p, l, r);
  int mid = (l + r) >> 1;
  if (ql <= mid) modify(p << 1, l, mid, ql, qr, x);
  if (qr > mid) modify(p << 1 | 1, mid + 1, r, ql, qr, x);
  merge(p, l, r);
}
Mat query(int p, int l, int r, int ql, int qr) {
  if (ql <= l && r <= qr) return ans[p] * c[l - ql];
  if (tag[p]) push_down(p, l, r);
  int mid = (l + r) >> 1;
  Mat r1, r2;
  if (ql <= mid) r1 = query(p << 1, l, mid, ql, qr);
  if (qr > mid) r2 = query(p << 1 | 1, mid + 1, r, ql, qr);
  return r1 + r2;
}
void dfs(int p, int l, int r) {
  printf("%d %d %d\n", p, l, r);
  ans[p].print();
  if (l == r) return;
  if (tag[p]) push_down(p, l, r);
  int mid = (l + r) >> 1;
  dfs(p << 1, l, mid), dfs(p << 1 | 1, mid + 1, r);
}
int main() {
  scanf("%d %d", &n, &q);
  for (int i = 1; i <= (int)n; i++) scanf("%d", &a[i]);
  init();
  build(1, 1, n);
  while (q--) {
    int op, l, r, x;
    scanf("%d %d %d", &op, &l, &r);
    if (op == 3) scanf("%d", &x);
    if (op == 1)
      update(1, 1, n, l, r);
    else if (op == 2)
      printf("%d\n", query(1, 1, n, l, r).a[0][0]);
    else
      modify(1, 1, n, l, r, x);
  }
  return 0;
}
