#include <bits/stdc++.h>
using namespace std;
long long mul(long long a, long long b) { return (a * b) % (1000000000); }
long long add(long long a, long long b) { return (a + b) % (1000000000); }
long long sub(long long a, long long b) {
  return (a - b + (a - b) / (1000000000) * (1000000000) + (1000000000)) %
         (1000000000);
}
int n, m;
long long f[(200000 + 10)], sf[(200000 + 10)] = {0}, f2[(200000 + 10)],
                                         sf2[(200000 + 10)];
struct arr_t {
  long long a[(200000 + 10) * 4], s0[(200000 + 10) * 4], s1[(200000 + 10) * 4],
      b[(200000 + 10) * 4];
  arr_t() {
    memset(a, 0, sizeof(a));
    memset(s0, 0, sizeof(s0));
    memset(s1, 0, sizeof(s1));
    memset(b, 0, sizeof(b));
  }
  long long S(int x, int n) {
    if (n == 1) return s0[x];
    if (n == 2) return s1[x];
    return add(mul(f[n - 2], s0[x]), mul(f[n - 1], s1[x]));
  }
  void update(int x, int l, int r) {
    int n = r - l + 1, m = (l + r) >> 1, ls = m - l + 1, rs = n - ls;
    s0[x] = (s0[(x << 1)] + S(((x << 1) + 1), ls + 1)) % (1000000000);
    s1[x] = (s1[(x << 1)] + S(((x << 1) + 1), ls + 2)) % (1000000000);
  }
  void change(int x, int n, int c) {
    s0[x] = add(s0[x], mul(sf[n], c));
    s1[x] = add(s1[x], mul(sf2[n], c));
  }
  void pushdown(int x, int l, int r) {
    if (l == r)
      return;
    else if (b[x]) {
      int n = r - l + 1, m = (l + r) >> 1, ls = m - l + 1, rs = n - ls;
      s0[(x << 1)] = add(s0[(x << 1)], mul(sf[ls], b[x]));
      s0[((x << 1) + 1)] = add(s0[((x << 1) + 1)], mul(sf[rs], b[x]));
      s1[(x << 1)] = add(s1[(x << 1)], mul(sf2[ls], b[x]));
      s1[((x << 1) + 1)] = add(s1[((x << 1) + 1)], mul(sf2[rs], b[x]));
      b[(x << 1)] += b[x];
      b[((x << 1) + 1)] += b[x];
      b[x] = 0;
    }
  }
  void ins(int x, int l, int r, int L, int R, int c) {
    pushdown(x, l, r);
    int n = r - l + 1, m = (l + r) >> 1;
    if (L <= l && r <= R) {
      b[x] += c;
      change(x, n, c);
      return;
    }
    if (L <= m) ins((x << 1), l, m, L, R, c);
    if (m < R) ins(((x << 1) + 1), m + 1, r, L, R, c);
    update(x, l, r);
  }
  void modify(int x, int l, int r, int L, int c) {
    pushdown(x, l, r);
    int n = r - l + 1, m = (l + r) >> 1;
    if (l == r) {
      s0[x] = s1[x] = c;
      return;
    }
    if (L <= m)
      modify((x << 1), l, m, L, c);
    else
      modify(((x << 1) + 1), m + 1, r, L, c);
    update(x, l, r);
  }
  void build(int x, int l, int r) {
    if (l == r) {
      scanf("%d", &a[x]);
      s0[x] = s1[x] = a[x];
      return;
    }
    int n = r - l + 1, m = (l + r) >> 1;
    build((x << 1), l, m);
    build(((x << 1) + 1), m + 1, r);
    update(x, l, r);
  }
  long long qur(int x, int l, int r, int L, int R) {
    pushdown(x, l, r);
    int n = r - l + 1, m = (l + r) >> 1;
    if (L <= l && r <= R) {
      return S(x, l - (L - 1));
    }
    long long ans = 0;
    if (L <= m) ans = add(ans, qur((x << 1), l, m, L, R));
    if (m < R) ans = add(ans, qur(((x << 1) + 1), m + 1, r, L, R));
    return ans;
  }
} T;
int main() {
  scanf("%d%d", &n, &m);
  f[1] = f[2] = sf[1] = 1, sf[2] = 2;
  for (int i = 3; i <= n; i++)
    f[i] = (f[i - 1] + f[i - 2]) % (1000000000),
    sf[i] = (sf[i - 1] + f[i]) % (1000000000);
  f2[1] = sf2[1] = 1, f2[2] = 2;
  sf2[2] = 3;
  for (int i = 3; i <= n; i++)
    f2[i] = (f2[i - 1] + f2[i - 2]) % (1000000000),
    sf2[i] = (sf2[i - 1] + f2[i]) % (1000000000);
  T.build(1, 1, n);
  for (int i = 1; i <= m; i++) {
    int p, x, v, l, r, d;
    scanf("%d", &p);
    if (p == 1) {
      scanf("%d%d", &x, &v);
      T.modify(1, 1, n, x, v);
    } else if (p == 2) {
      scanf("%d%d", &l, &r);
      cout << T.qur(1, 1, n, l, r) << endl;
    } else {
      scanf("%d%d%d", &l, &r, &d);
      T.ins(1, 1, n, l, r, d);
    }
  }
  return 0;
}
