#include <bits/stdc++.h>
using namespace std;
inline int in() {
  int x;
  scanf("%d", &x);
  return x;
}
const int N = 2 * 1e5 + 10;
const long long MOD = 1e9;
const long double eps = 1e-12;
int n, m;
long long fib[N], fib_sum[N], g0[4 * N], g1[4 * N], lazy[4 * N];
void precalc() {
  fib[0] = fib[1] = 1;
  for (int i = 2; i < N; i++) fib[i] = (fib[i - 1] + fib[i - 2]) % MOD;
  for (int i = 0; i < N; i++) fib_sum[i + 1] = (fib_sum[i] + fib[i]) % MOD;
}
long long get_gib(int i, int x) {
  if (x == 0) return g0[i];
  if (x == 1) return g1[i];
  long long res = 0;
  res = g0[i] * fib[x - 2] + g1[i] * fib[x - 1];
  res %= MOD;
  return res;
}
void pull(int i, int l, int r) {
  int m = (l + r) / 2, cl = i * 2 + 0, cr = i * 2 + 1;
  g0[i] = g0[cl] + get_gib(cr, m - l);
  g0[i] %= MOD;
  g1[i] = g1[cl] + get_gib(cr, m - l + 1);
  g1[i] %= MOD;
}
void upd(int id, int len, int add) {
  g0[id] += add * fib_sum[len];
  g0[id] %= MOD;
  g1[id] += add * fib_sum[len + 1] - add;
  g1[id] %= MOD;
}
void push(int idx, int l, int r) {
  if (lazy[idx] <= 0) return;
  int a = lazy[idx], cl = idx * 2 + 0, cr = idx * 2 + 1, m = (l + r) / 2;
  upd(cl, m - l, a);
  upd(cr, r - m, a);
  lazy[cl] += a;
  lazy[cr] += a;
}
void turn(int pos, int val, int l = 0, int r = n, int idx = 1) {
  if (pos < l || r <= pos) return;
  if (r - l < 2) {
    g0[idx] = val, g1[idx] = val;
    return;
  }
  push(idx, l, r);
  int m = (l + r) / 2;
  turn(pos, val, l, m, idx * 2 + 0);
  turn(pos, val, m, r, idx * 2 + 1);
  pull(idx, l, r);
}
void inc(int ql, int qr, int val, int l = 0, int r = n, int idx = 1) {
  if (qr <= l || r <= ql) return;
  if (ql <= l && r <= qr) {
    upd(idx, r - l, val);
    lazy[idx] += val;
    return;
  }
  push(idx, l, r);
  int m = (l + r) / 2;
  inc(ql, qr, l, m, idx * 2 + 0);
  inc(ql, qr, m, r, idx * 2 + 1);
  pull(idx, l, r);
}
long long get(int ql, int qr, int l = 0, int r = n, int idx = 1) {
  if (qr <= l || r <= ql) return 0;
  if (ql <= l && r <= qr) {
    return get_gib(idx, l - ql);
  }
  push(idx, l, r);
  long long res = 0;
  int m = (l + r) / 2;
  res += get(ql, qr, l, m, idx * 2 + 0);
  res += get(ql, qr, m, r, idx * 2 + 1);
  return res % MOD;
}
int main() {
  precalc();
  n = in();
  m = in();
  for (int i = 0; i < n; i++) {
    int a = in();
    turn(i, a);
  }
  for (int i = 0; i < m; i++) {
    int t = in();
    if (t == 1) {
      int x = in(), v = in();
      x--;
      turn(x, v);
    } else if (t == 2) {
      int l = in(), r = in();
      l--;
      long long res = (get(l, r) + MOD) % MOD;
      printf("%I64d\n", res);
    } else {
      int l = in(), r = in(), d = in();
      l--;
      inc(l, r, d);
    }
  }
  return 0;
}
