#include <bits/stdc++.h>
using namespace std;
const int md = 1000000000;
inline void sad(int &a, int b) {
  a += b;
  while (a >= md) a -= md;
  while (a < 0) a += md;
}
inline int add(int a, int b) {
  int ret = a + b;
  while (ret >= md) ret -= md;
  while (ret < 0) ret += md;
  return ret;
}
inline int mul(int a, int b) {
  int ret = 1ll * a * b % md;
  while (ret >= md) ret -= md;
  while (ret < 0) ret += md;
  return ret;
}
struct vec {
  int len;
  int a[2];
};
struct mat {
  int a[2][2];
};
inline vec operator*(const mat &a, const vec &b) {
  vec ret;
  ret.len = b.len;
  ret.a[0] = add(mul(a.a[0][0], b.a[0]), mul(a.a[0][1], b.a[1]));
  ret.a[1] = add(mul(a.a[1][0], b.a[0]), mul(a.a[1][1], b.a[1]));
  return ret;
}
inline mat operator*(const mat &a, const mat &b) {
  mat ret;
  for (int i = 0; i < 2; ++i) {
    for (int j = 0; j < 2; ++j) {
      ret.a[i][j] = 0;
      for (int k = 0; k < 2; ++k) {
        sad(ret.a[i][j], mul(a.a[i][k], b.a[k][j]));
      }
    }
  }
  return ret;
}
mat tpr[200010];
mat sfb;
vec vod;
inline vec operator*(const vec &a, const vec &b) {
  if (!a.len) return b;
  if (!b.len) return a;
  vec ret = tpr[a.len] * b;
  sad(ret.a[0], a.a[0]);
  sad(ret.a[1], a.a[1]);
  ret.len = a.len + b.len;
  return ret;
}
vec pre[200010];
int init[200010];
vec a[524333];
int ad[524333];
inline void pushdn(int i, int l, int r) {
  if (!ad[i]) {
    return;
  }
  int t = ad[i];
  ad[i] = 0;
  vec cur = pre[a[i].len];
  cur.a[0] = mul(cur.a[0], t);
  cur.a[1] = mul(cur.a[1], t);
  sad(a[i].a[0], cur.a[0]);
  sad(a[i].a[1], cur.a[1]);
  if (l == r) return;
  sad(ad[i << 1], t);
  sad(ad[i << 1 | 1], t);
}
void build(int i, int l, int r) {
  if (l == r) {
    a[i].len = 1;
    a[i].a[0] = init[l];
    a[i].a[1] = 0;
    ad[i] = 0;
    return;
  }
  register int md = (l + r) >> 1;
  build(i << 1, l, md);
  build(i << 1 | 1, md + 1, r);
  a[i] = a[i << 1] * a[i << 1 | 1];
}
vec query(int i, int l, int r, int lt, int rt) {
  if (l > rt || r < lt) return vod;
  pushdn(i, l, r);
  if (lt <= l && rt >= r) {
    return a[i];
  }
  register int md = (l + r) >> 1;
  return query(i << 1, l, md, lt, rt) * query(i << 1 | 1, md + 1, r, lt, rt);
}
void modify(int i, int l, int r, int pos, int val) {
  pushdn(i, l, r);
  if (l > pos || r < pos) return;
  if (l == r) {
    a[i].a[0] = val;
    a[i].a[1] = 0;
    ad[i] = 0;
    return;
  }
  register int md = (l + r) >> 1;
  modify(i << 1, l, md, pos, val);
  modify(i << 1 | 1, md + 1, r, pos, val);
  a[i] = a[i << 1] * a[i << 1 | 1];
}
void add(int i, int l, int r, int lt, int rt, int val) {
  pushdn(i, l, r);
  if (l > rt || r < lt) return;
  if (lt <= l && rt >= r) {
    ad[i] = val;
    pushdn(i, l, r);
    return;
  }
  register int md = (l + r) >> 1;
  add(i << 1, l, md, lt, rt, val);
  add(i << 1 | 1, md + 1, r, lt, rt, val);
  a[i] = a[i << 1] * a[i << 1 | 1];
}
int main(void) {
  vod.len = 0;
  vod.a[0] = vod.a[1] = 0;
  sfb.a[0][0] = 1;
  sfb.a[0][1] = 1;
  sfb.a[1][0] = 1;
  sfb.a[1][1] = 0;
  pre[1].a[0] = 1;
  pre[1].a[1] = 0;
  tpr[0].a[0][0] = tpr[0].a[1][1] = 1;
  tpr[0].a[0][1] = tpr[0].a[1][0] = 0;
  tpr[1] = sfb;
  for (int i = 2; i <= 200000; ++i) {
    pre[i] = sfb * pre[i - 1];
    sad(pre[i].a[0], 1);
    tpr[i] = tpr[i - 1] * sfb;
  }
  int n, q;
  scanf("%d%d", &n, &q);
  for (int i = 1; i <= n; ++i) {
    scanf("%d", &init[i]);
  }
  build(1, 1, n);
  int tpe, a, b, c;
  while (q--) {
    scanf("%d%d%d", &tpe, &a, &b);
    switch (tpe) {
      case 1: {
        modify(1, 1, n, a, b);
        break;
      }
      case 2: {
        vec res = query(1, 1, n, a, b);
        printf("%d\n", res.a[0]);
        break;
      }
      case 3: {
        scanf("%d", &c);
        add(1, 1, n, a, b, c);
        break;
      }
    }
  }
  return 0;
}
