#include <bits/stdc++.h>
using namespace std;
long long fib[200005][2][2];
int A[200005], lazy[800005];
struct ret {
  pair<long long, long long> r;
  int sz;
};
pair<long long, long long> tree[800005];
pair<long long, long long> add(pair<long long, long long> a,
                               pair<long long, long long> b) {
  return {(a.first + b.first) % 1000000000, (a.second + b.second) % 1000000000};
}
void build_tree(int node, int a, int b) {
  if (a > b) return;
  if (a == b) {
    tree[node] = {A[a], 0};
    return;
  }
  build_tree(node * 2, a, (a + b) / 2);
  build_tree(node * 2 + 1, 1 + (a + b) / 2, b);
  int sz = (a + b) / 2 - a + 1;
  pair<long long, long long> tmp = {
      (fib[sz][0][0] * tree[node * 2 + 1].first +
       fib[sz][0][1] * tree[node * 2 + 1].second) %
          1000000000,
      (fib[sz][1][0] * tree[node * 2 + 1].first +
       fib[sz][1][1] * tree[node * 2 + 1].second) %
          1000000000};
  tree[node] = add(tree[node * 2], tmp);
}
void update(int node, int a, int b, int index, int val) {
  if (lazy[node] != 0) {
    tree[node] = {
        (tree[node].first + lazy[node] * (fib[b - a + 2][0][0] - 1)) %
            1000000000,
        (tree[node].second + lazy[node] * (fib[b - a + 1][0][0] - 1)) %
            1000000000};
    if (a != b) {
      lazy[node * 2] += lazy[node];
      if (lazy[node * 2] >= 1000000000) lazy[node * 2] -= 1000000000;
      lazy[node * 2 + 1] += lazy[node];
      if (lazy[node * 2 + 1] >= 1000000000) lazy[node * 2 + 1] -= 1000000000;
    }
    lazy[node] = 0;
  }
  if (index < a || index > b) return;
  if (a == b) {
    tree[node] = {val, 0};
    return;
  }
  update(2 * node, a, (a + b) / 2, index, val);
  update(2 * node + 1, (a + b) / 2 + 1, b, index, val);
  int sz = (a + b) / 2 - a + 1;
  pair<long long, long long> tmp = {
      (fib[sz][0][0] * tree[node * 2 + 1].first +
       fib[sz][0][1] * tree[node * 2 + 1].second) %
          1000000000,
      (fib[sz][1][0] * tree[node * 2 + 1].first +
       fib[sz][1][1] * tree[node * 2 + 1].second) %
          1000000000};
  tree[node] = add(tree[node * 2], tmp);
}
void update_tree(int node, int a, int b, int i, int j, int value) {
  if (a > b || a > j || b < i) return;
  if (lazy[node] != 0) {
    tree[node] = {
        (tree[node].first + lazy[node] * (fib[b - a + 2][0][0] - 1)) %
            1000000000,
        (tree[node].second + lazy[node] * (fib[b - a + 1][0][0] - 1)) %
            1000000000};
    if (a != b) {
      lazy[node * 2] += lazy[node];
      if (lazy[node * 2] >= 1000000000) lazy[node * 2] -= 1000000000;
      lazy[node * 2 + 1] += lazy[node];
      if (lazy[node * 2 + 1] >= 1000000000) lazy[node * 2 + 1] -= 1000000000;
    }
    lazy[node] = 0;
  }
  if (a >= i && b <= j) {
    tree[node] = {
        (tree[node].first + value * (fib[b - a + 2][0][0] - 1)) % 1000000000,
        (tree[node].second + value * (fib[b - a + 1][0][0] - 1)) % 1000000000};
    if (a != b) {
      lazy[node * 2] += value;
      if (lazy[node * 2] >= 1000000000) lazy[node * 2] -= 1000000000;
      lazy[node * 2 + 1] += value;
      if (lazy[node * 2 + 1] >= 1000000000) lazy[node * 2 + 1] -= 1000000000;
    }
    return;
  }
  update_tree(node * 2, a, (a + b) / 2, i, j, value);
  update_tree(1 + node * 2, 1 + (a + b) / 2, b, i, j, value);
  int sz = (a + b) / 2 - a + 1;
  pair<long long, long long> tmp = {
      (fib[sz][0][0] * tree[node * 2 + 1].first +
       fib[sz][0][1] * tree[node * 2 + 1].second) %
          1000000000,
      (fib[sz][1][0] * tree[node * 2 + 1].first +
       fib[sz][1][1] * tree[node * 2 + 1].second) %
          1000000000};
  tree[node] = add(tree[node * 2], tmp);
}
ret query_tree(int node, int a, int b, int i, int j) {
  if (a > b || a > j || b < i) return {{0, 0}, 0};
  if (lazy[node] != 0) {
    tree[node] = {
        (tree[node].first + lazy[node] * (fib[b - a + 2][0][0] - 1)) %
            1000000000,
        (tree[node].second + lazy[node] * (fib[b - a + 1][0][0] - 1)) %
            1000000000};
    if (a != b) {
      lazy[node * 2] += lazy[node];
      if (lazy[node * 2] >= 1000000000) lazy[node * 2] -= 1000000000;
      lazy[node * 2 + 1] += lazy[node];
      if (lazy[node * 2 + 1] >= 1000000000) lazy[node * 2 + 1] -= 1000000000;
    }
    lazy[node] = 0;
  }
  if (a >= i && b <= j) return {tree[node], b - a + 1};
  ret q1 = query_tree(node * 2, a, (a + b) / 2, i, j);
  ret q2 = query_tree(1 + node * 2, 1 + (a + b) / 2, b, i, j);
  pair<long long, long long> tmp = {
      (fib[q1.sz][0][0] * q2.r.first + fib[q1.sz][0][1] * q2.r.second) %
          1000000000,
      (fib[q1.sz][1][0] * q2.r.first + fib[q1.sz][1][1] * q2.r.second) %
          1000000000};
  ret res = {add(q1.r, tmp), q1.sz + q2.sz};
  return res;
}
int main() {
  int i, n, m, t, x, v, d;
  fib[0][0][0] = fib[0][1][1] = 1;
  for (i = 1; i < 200005; i++) {
    fib[i][0][0] = (fib[i - 1][0][0] + fib[i - 1][1][0]) % 1000000000;
    fib[i][0][1] = (fib[i - 1][0][1] + fib[i - 1][1][1]) % 1000000000;
    fib[i][1][0] = fib[i - 1][0][0];
    fib[i][1][1] = fib[i - 1][0][1];
  }
  scanf("%d%d", &n, &m);
  for (i = 1; i <= n; i++) scanf("%d", &A[i]);
  build_tree(1, 1, n);
  while (m--) {
    scanf("%d%d%d", &t, &x, &v);
    if (t == 1)
      update(1, 1, n, x, v);
    else if (t == 2)
      printf("%lld\n", query_tree(1, 1, n, x, v).r.first);
    else {
      scanf("%d", &d);
      update_tree(1, 1, n, x, v, d);
    }
  }
  return 0;
}
