#include <bits/stdc++.h>
#pragma comment(linker, "/STACK:16777216")
using namespace std;
const double eps = 1e-9;
const double pi = acos(-1.0);
const int maxn = (int)1e5 + 10;
const int mod = (int)1e9;
int f[maxn], pf[maxn], t[4 * maxn][2], add[4 * maxn], a[maxn];
int get(int idx, int pw) {
  if (pw < 2) return t[idx][pw];
  return (t[idx][1] * (long long)f[pw - 1] % mod +
          t[idx][0] * (long long)f[pw - 2] % mod) %
         mod;
}
void push(int l, int r, int idx) {
  if (!add[idx]) return;
  int m = (l + r) >> 1;
  add[2 * idx] += add[idx];
  add[2 * idx] %= mod;
  add[2 * idx + 1] += add[idx];
  add[2 * idx + 1] %= mod;
  t[2 * idx][0] += pf[m - l] * (long long)add[idx] % mod;
  t[2 * idx][0] %= mod;
  t[2 * idx][1] += (pf[m - l + 1] + mod - 1) * (long long)add[idx] % mod;
  t[2 * idx][1] %= mod;
  t[2 * idx + 1][0] += pf[r - m - 1] * (long long)add[idx] % mod;
  t[2 * idx + 1][0] %= mod;
  t[2 * idx + 1][1] += (pf[r - m] + mod - 1) * (long long)add[idx] % mod;
  t[2 * idx + 1][1] %= mod;
  add[idx] = 0;
}
void build(int l, int r, int idx) {
  if (l == r) {
    t[idx][0] = a[l];
    t[idx][1] = a[l];
  } else {
    int m = (l + r) >> 1;
    build(l, m, 2 * idx);
    build(m + 1, r, 2 * idx + 1);
    t[idx][0] = (get(2 * idx, 0) + get(2 * idx + 1, m - l + 1)) % mod;
    t[idx][1] = (get(2 * idx, 1) + get(2 * idx + 1, m - l + 2)) % mod;
  }
}
void PUT(int l, int r, int pos, int idx, int val) {
  if (pos < l || r < pos) return;
  if (l == r) {
    t[idx][0] = val;
    t[idx][1] = val;
  } else {
    push(l, r, idx);
    int m = (l + r) >> 1;
    PUT(l, m, pos, 2 * idx, val);
    PUT(m + 1, r, pos, 2 * idx + 1, val);
    t[idx][0] = (get(2 * idx, 0) + get(2 * idx + 1, m - l + 1)) % mod;
    t[idx][1] = (get(2 * idx, 1) + get(2 * idx + 1, m - l + 2)) % mod;
  }
}
void ADD(int l, int r, int a, int b, int idx, int val) {
  if (b < l || r < a) return;
  if (a <= l && r <= b) {
    add[idx] += val;
    add[idx] %= mod;
    t[idx][0] += pf[r - l] * (long long)val % mod;
    t[idx][0] %= mod;
    t[idx][1] += (pf[r - l + 1] + mod - 1) * (long long)val % mod;
    t[idx][1] %= mod;
  } else {
    push(l, r, idx);
    int m = (l + r) >> 1;
    ADD(l, m, a, b, 2 * idx, val);
    ADD(m + 1, r, a, b, 2 * idx + 1, val);
    t[idx][0] = (get(2 * idx, 0) + get(2 * idx + 1, m - l + 1)) % mod;
    t[idx][1] = (get(2 * idx, 1) + get(2 * idx + 1, m - l + 2)) % mod;
  }
}
int GET(int l, int r, int a, int b, int idx, int pw) {
  if (a == l && b == r) {
    return get(idx, pw);
  } else {
    push(l, r, idx);
    int m = (l + r) >> 1;
    if (b <= m) return GET(l, m, a, b, 2 * idx, pw);
    if (a > m) return GET(m + 1, r, a, b, 2 * idx + 1, pw);
    return (GET(l, m, a, m, 2 * idx, pw) +
            GET(m + 1, r, m + 1, b, 2 * idx + 1, pw + m - a + 1)) %
           mod;
  }
}
int main() {
  int n, m;
  cin >> n >> m;
  for (int i = 0; i < n; i++) {
    scanf("%d", &a[i]);
  }
  f[0] = 1;
  f[1] = 1;
  for (int i = 2; i <= n; i++) {
    f[i] = f[i - 1] + f[i - 2];
    f[i] %= mod;
  }
  pf[0] = f[0];
  for (int i = 1; i <= n; i++) {
    pf[i] = pf[i - 1] + f[i];
    pf[i] %= mod;
  }
  build(0, n - 1, 1);
  for (int i = 0; i < m; i++) {
    int tt;
    scanf("%d", &tt);
    if (tt == 1) {
      int p, v;
      scanf("%d%d", &p, &v);
      --p;
      PUT(0, n - 1, p, 1, v);
    } else if (tt == 2) {
      int l, r;
      scanf("%d%d", &l, &r);
      --l;
      --r;
      printf("%d\n", GET(0, n - 1, l, r, 1, 0));
    } else {
      int l, r, v;
      scanf("%d%d%d", &l, &r, &v);
      --l;
      --r;
      ADD(0, n - 1, l, r, 1, v);
    }
  }
  return 0;
}
