#include <bits/stdc++.h>
using namespace std;
inline char gc() {
  static char buf[100000], *p1 = buf, *p2 = buf;
  return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2)
             ? EOF
             : *p1++;
}
inline long long read() {
  long long x = 0;
  char ch = getchar();
  bool positive = 1;
  for (; !isdigit(ch); ch = getchar())
    if (ch == '-') positive = 0;
  for (; isdigit(ch); ch = getchar()) x = x * 10 + ch - '0';
  return positive ? x : -x;
}
inline void write(long long x) {
  if (x < 0) x = -x, putchar('-');
  if (x > 9) write(x / 10);
  putchar(x % 10 + '0');
}
inline void writeln(long long x) {
  write(x);
  puts("");
}
const int wzp = 1e9;
struct Matrix {
  long long a[2][2];
  inline Matrix operator*(Matrix x) {
    Matrix ans;
    for (long long i = 0; i <= 1; i++) {
      for (long long j = 0; j <= 1; j++) {
        ans.a[i][j] = 0;
        for (long long k = 0; k <= 1; k++) {
          ans.a[i][j] = (ans.a[i][j] + a[i][k] * x.a[k][j]) % wzp;
        }
      }
    }
    return ans;
  }
  inline Matrix operator+(Matrix x) {
    Matrix ans;
    for (long long i = 0; i <= 1; i++) {
      for (long long j = 0; j <= 1; j++) {
        ans.a[i][j] = (a[i][j] + x.a[i][j]) % wzp;
      }
    }
    return ans;
  }
  inline void wr() {
    cout << a[0][0] << " " << a[0][1] << endl;
    cout << a[1][0] << " " << a[1][1] << endl;
  }
} num[200005], sum[200005];
struct Ans {
  long long a[2];
  inline Ans operator+(Ans x) {
    Ans ans;
    ans.a[0] = (a[0] + x.a[0]) % wzp;
    ans.a[1] = (a[1] + x.a[1]) % wzp;
    return ans;
  }
  inline Ans operator*(Matrix x) {
    Ans ans;
    ans.a[0] = ans.a[1] = 0;
    for (long long i = 0; i <= 1; i++) {
      for (long long j = 0; j <= 1; j++) {
        ans.a[i] = (ans.a[i] + a[j] * x.a[j][i]) % wzp;
      }
    }
    return ans;
  }
};
struct Tree {
  long long l, r, lazy;
  Ans num;
} st[200005 * 4];
long long n, m, l, r, k, opt, a[200005];
inline void up(long long node) {
  long long len = st[node << 1].r - st[node << 1].l + 1;
  st[node].num = st[node << 1].num + st[node << 1 | 1].num * num[len];
  return;
}
inline void down(long long node) {
  if (!st[node].lazy) return;
  long long now = st[node].lazy, lenl = st[node << 1].r - st[node << 1].l,
            lenr = st[node << 1 | 1].r - st[node << 1 | 1].l;
  st[node].lazy = 0;
  st[node << 1].lazy = (st[node << 1].lazy + now) % wzp;
  st[node << 1 | 1].lazy = (st[node << 1 | 1].lazy + now) % wzp;
  st[node << 1].num = st[node << 1].num + (Ans){now, now} * sum[lenl];
  st[node << 1 | 1].num = st[node << 1 | 1].num + (Ans){now, now} * sum[lenr];
  return;
}
inline void build(long long node, long long l, long long r) {
  st[node].l = l;
  st[node].r = r;
  if (l == r) {
    st[node].num = (Ans){a[l], a[l]};
    return;
  }
  long long mid = (l + r) >> 1;
  build(node << 1, l, mid);
  build(node << 1 | 1, mid + 1, r);
  up(node);
  return;
}
inline void change1(long long node, long long id, long long k) {
  if (st[node].l == st[node].r) {
    st[node].num = (Ans){k, k};
    return;
  }
  down(node);
  long long mid = (st[node].l + st[node].r) >> 1;
  if (id <= mid) {
    change1(node << 1, id, k);
  } else {
    change1(node << 1 | 1, id, k);
  }
  up(node);
  return;
}
inline void change2(long long node, long long l, long long r, long long k) {
  if (st[node].l > r || st[node].r < l) return;
  if (st[node].l >= l && st[node].r <= r) {
    long long len = st[node].r - st[node].l;
    st[node].lazy = (st[node].lazy + k) % wzp;
    st[node].num = st[node].num + (Ans){k, k} * sum[len];
    return;
  }
  down(node);
  change2(node << 1, l, r, k);
  change2(node << 1 | 1, l, r, k);
  up(node);
  return;
}
inline Ans query(long long node, long long l, long long r) {
  if (st[node].l >= l && st[node].r <= r) {
    return st[node].num;
  }
  down(node);
  long long mid = (st[node].l + st[node].r) >> 1;
  if (r <= mid) return query(node << 1, l, r);
  if (l > mid) return query(node << 1 | 1, l, r);
  Ans ans;
  ans.a[0] = ans.a[1] = 0;
  ans = query(node << 1, l, mid) +
        query(node << 1 | 1, mid + 1, r) * num[mid - l + 1];
  return ans;
}
int main() {
  n = read();
  m = read();
  for (long long i = 1; i <= n; i++) a[i] = read();
  num[0].a[0][0] = 1;
  num[0].a[1][1] = 1;
  sum[0] = num[0];
  num[1].a[1][1] = 0;
  num[1].a[0][0] = num[1].a[0][1] = num[1].a[1][0] = 1;
  sum[1] = sum[0] + num[1];
  for (long long i = 2; i <= n; i++) {
    num[i] = num[i - 1] * num[1];
    sum[i] = sum[i - 1] + num[i];
  }
  build(1, 1, n);
  for (long long i = 1; i <= m; i++) {
    opt = read();
    if (opt == 1) {
      l = read();
      k = read();
      change1(1, l, k);
    }
    if (opt == 2) {
      l = read();
      r = read();
      writeln(query(1, l, r).a[1]);
    }
    if (opt == 3) {
      l = read();
      r = read();
      k = read();
      change2(1, l, r, k);
    }
  }
  return 0;
}
