#include <bits/stdc++.h>
using namespace std;
const int modo = 1000000000;
int val1[1 << 19], val2[1 << 19];
int tag[1 << 19];
int fib[200005];
int sum_fib[200005];
int a[200005];
void update_ans(int num, int l, int r) {
  int mid = (l + r) / 2;
  val1[num] = (val1[num * 2 + 1] + (long long)val1[num * 2 + 2] * fib[mid - l] +
               (long long)val2[num * 2 + 2] * fib[mid - l + 1]) %
              modo;
  val2[num] =
      (val2[num * 2 + 1] + (long long)val1[num * 2 + 2] * fib[mid - l + 1] +
       (long long)val2[num * 2 + 2] * fib[mid - l + 2]) %
      modo;
}
void push_down(int num, int l, int r) {
  if (tag[num] == 0) return;
  int mid = (l + r) / 2;
  val1[num * 2 + 1] =
      (val1[num * 2 + 1] + (long long)sum_fib[mid - l] * tag[num] + tag[num]) %
      modo;
  val2[num * 2 + 1] =
      (val2[num * 2 + 1] + (long long)sum_fib[mid - l + 1] * tag[num]) % modo;
  val1[num * 2 + 2] =
      (val1[num * 2 + 2] + (long long)sum_fib[r - mid] * tag[num] + tag[num]) %
      modo;
  val2[num * 2 + 2] =
      (val2[num * 2 + 2] + (long long)sum_fib[r - mid + 1] * tag[num]) % modo;
  tag[num] = 0;
}
void build_tree(int num, int l, int r) {
  if (l == r - 1) {
    val1[num] = a[l];
    val2[num] = 0;
    return;
  }
  int mid = (l + r) / 2;
  build_tree(num * 2 + 1, l, mid);
  build_tree(num * 2 + 2, mid, r);
  update_ans(num, l, r);
}
int query(int num, int l, int r, int l0, int r0, int t) {
  if ((l0 <= l) && (r <= r0)) {
    return ((long long)val1[num] * fib[t] + (long long)val2[num] * fib[t + 1]) %
           modo;
  }
  int sum = 0;
  push_down(num, l, r);
  int mid = (l + r) / 2;
  if (l0 < mid) sum += query(num * 2 + 1, l, mid, l0, r0, t);
  if (mid < r0) sum += query(num * 2 + 2, mid, r, l0, r0, t + (mid - l));
  return sum % modo;
}
void change1(int num, int l, int r, int loc, int t) {
  if (l == r - 1) {
    val1[num] = t;
    val2[num] = 0;
    return;
  }
  push_down(num, l, r);
  int mid = (l + r) / 2;
  if (loc < mid)
    change1(num * 2 + 1, l, mid, loc, t);
  else
    change1(num * 2 + 2, mid, r, loc, t);
  update_ans(num, l, r);
}
void change2(int num, int l, int r, int l0, int r0, int t) {
  if ((l0 <= l) && (r <= r0)) {
    val1[num] = (val1[num] + (long long)sum_fib[r - l] * t) % modo;
    val2[num] = (val2[num] + (long long)sum_fib[r - l + 1] * t - t) % modo;
    tag[num] += t;
    return;
  }
  push_down(num, l, r);
  int mid = (l + r) / 2;
  if (l0 < mid) change2(num * 2 + 1, l, mid, l0, r0, t);
  if (mid < r0) change2(num * 2 + 2, mid, r, l0, r0, t);
  update_ans(num, l, r);
}
int main() {
  int i;
  fib[0] = 1;
  fib[1] = 0;
  sum_fib[0] = 1;
  sum_fib[1] = 1;
  for (i = 2; i <= 200002; i++) {
    fib[i] = (fib[i - 1] + fib[i - 2]) % modo;
    sum_fib[i] = (sum_fib[i - 1] + fib[i]) % modo;
  }
  int n, m;
  scanf("%d%d", &n, &m);
  for (i = 0; i < n; i++) {
    scanf("%d", &a[i]);
  }
  build_tree(0, 0, n);
  for (i = 0; i < m; i++) {
    int oper;
    scanf("%d", &oper);
    if (oper == 1) {
      int loc, val;
      scanf("%d%d", &loc, &val);
      loc--;
      change1(0, 0, n, loc, val);
    } else if (oper == 2) {
      int l, r;
      scanf("%d%d", &l, &r);
      l--;
      printf("%d\n", query(0, 0, n, l, r, 2 - l));
    } else {
      int l, r, x;
      scanf("%d%d%d", &l, &r, &x);
      l--;
      change2(0, 0, n, l, r, x);
    }
  }
  return 0;
}
