#include <bits/stdc++.h>
using namespace std;
const int N = 3e5 + 66;
int n, m, v[N];
inline char gc() {
  static char buf[1000000], *p1 = buf, *p2 = buf;
  return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1000000, stdin), p1 == p2)
             ? EOF
             : *p1++;
}
inline long long read() {
  long long x = 0;
  char ch = getchar(), w = 1;
  while (ch < '0' || ch > '9') {
    if (ch == '-') w = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  return x * w;
}
void write(long long x) {
  if (x < 0) putchar('-'), x = -x;
  if (x > 9) write(x / 10);
  putchar(x % 10 + '0');
}
inline void writeln(long long x) {
  write(x);
  puts("");
}
const long long p = 1e9;
void add(long long &x, long long v) {
  x += v;
  if (x >= p) x %= p;
  if (x < 0) x = (x % p + p) % p;
}
struct Matrix {
  long long a[2][2];
  Matrix() { memset(a, 0, sizeof a); }
  Matrix operator*(Matrix b) const {
    Matrix c;
    for (int i = 0; i < 2; ++i)
      for (int j = 0; j < 2; ++j)
        for (int k = 0; k < 2; ++k) add(c.a[i][j], a[i][k] * b.a[k][j]);
    return c;
  }
  Matrix operator+(Matrix b) const {
    Matrix c;
    for (int i = 0; i < 2; ++i)
      for (int j = 0; j < 2; ++j) add(c.a[i][j], a[i][j] + b.a[i][j]);
    return c;
  }
} B[N];
long long f[N];
struct T {
  Matrix v;
  int l, r;
  long long add;
} t[N * 4];
void up(int o) {
  t[o].v =
      t[(o << 1)].v + t[(o << 1 | 1)].v * B[t[(o << 1)].r - t[(o << 1)].l + 1];
}
void build(int o, int l, int r) {
  t[o].l = l, t[o].r = r;
  if (l == r) {
    t[o].v.a[0][0] = t[o].v.a[0][1] = v[l];
    return;
  }
  int mid = (l + r) >> 1;
  if (l <= mid) build((o << 1), l, mid);
  if (r > mid) build((o << 1 | 1), mid + 1, r);
  up(o);
}
void down(int o) {
  if (t[o].add) {
    add(t[(o << 1)].v.a[0][0], t[o].add * f[t[(o << 1)].r - t[(o << 1)].l] % p);
    add(t[(o << 1)].v.a[0][1],
        t[o].add * (f[t[(o << 1)].r - t[(o << 1)].l + 1] - 1) % p);
    add(t[(o << 1 | 1)].v.a[0][0],
        t[o].add * f[t[(o << 1 | 1)].r - t[(o << 1 | 1)].l] % p);
    add(t[(o << 1 | 1)].v.a[0][1],
        t[o].add * (f[t[(o << 1 | 1)].r - t[(o << 1 | 1)].l + 1] - 1) % p);
    add(t[(o << 1)].add, t[o].add);
    add(t[(o << 1 | 1)].add, t[o].add);
    t[o].add = 0;
  }
}
void ins(int o, int x, int v) {
  if (t[o].l == t[o].r) {
    t[o].v.a[0][0] = t[o].v.a[0][1] = v;
    return;
  }
  int mid = (t[o].l + t[o].r) >> 1;
  down(o);
  if (x <= mid)
    ins((o << 1), x, v);
  else
    ins((o << 1 | 1), x, v);
  up(o);
}
Matrix query(int o, int l, int r) {
  if (t[o].l >= l && t[o].r <= r) return t[o].v;
  if (t[o].l == t[o].r) return t[0].v;
  int mid = (t[o].l + t[o].r) >> 1;
  down(o);
  if (r <= mid) return query((o << 1), l, r);
  if (l > mid) return query((o << 1 | 1), l, r);
  Matrix lt = query((o << 1), l, r);
  Matrix rt = query((o << 1 | 1), l, r);
  return lt + rt * B[mid - max(l, t[(o << 1)].l) + 1];
}
void chg(int o, int l, int r, int v) {
  if (l <= t[o].l && r >= t[o].r) {
    add(t[o].v.a[0][0], v * f[t[o].r - t[o].l] % p);
    add(t[o].v.a[0][1], v * (f[t[o].r - t[o].l + 1] - 1) % p);
    t[o].add += v;
    return;
  }
  int mid = (t[o].l + t[o].r) >> 1;
  down(o);
  if (l <= mid) chg((o << 1), l, r, v);
  if (r > mid) chg((o << 1 | 1), l, r, v);
  up(o);
}
int main() {
  n = read(), m = read();
  B[0].a[0][1] = 1;
  B[0].a[1][0] = B[0].a[1][1] = 1;
  B[1] = B[0];
  for (int i = 2; i <= n; ++i) B[i] = B[i - 1] * B[0];
  B[0].a[0][0] = B[0].a[1][1] = 1;
  B[0].a[1][0] = B[0].a[0][1] = 0;
  for (int i = 1; i <= n; ++i) v[i] = read();
  f[0] = f[1] = 1;
  for (int i = 2; i <= n; ++i) f[i] = (f[i - 1] + f[i - 2]) % p;
  for (int i = 1; i <= n; ++i) f[i] = (f[i - 1] + f[i]) % p;
  build(1, 1, n);
  int x, v, l, r, d, op;
  for (int T = 1; T <= m; ++T) {
    op = read();
    if (op == 1) {
      x = read(), v = read();
      ins(1, x, v);
    } else if (op == 2) {
      l = read(), r = read();
      writeln(query(1, l, r).a[0][0]);
    } else if (op == 3) {
      l = read(), r = read(), d = read();
      chg(1, l, r, d);
    }
  }
  return 0;
}
