#include <bits/stdc++.h>
using namespace std;
const long long p = 1000000000;
pair<long long, long long> A[262150], S[262150];
struct Tnode {
  pair<long long, long long> key;
  long long tag;
} T[524288];
long long a[262150], F[262150], G[262150];
int n, m, N;
inline pair<long long, long long> operator+(pair<long long, long long> A,
                                            pair<long long, long long> B) {
  return make_pair((A.first + B.first) % p, (A.second + B.second) % p);
}
inline pair<long long, long long> operator-(pair<long long, long long> A,
                                            pair<long long, long long> B) {
  return make_pair((A.first - B.first + p) % p, (A.second - B.second + p) % p);
}
inline pair<long long, long long> operator*(pair<long long, long long> A,
                                            long long B) {
  return make_pair((A.first * B) % p, (A.second * B) % p);
}
void build(int i, int l, int r) {
  int mid;
  T[i].tag = 0;
  if (l == r)
    T[i].key = A[l] * a[l];
  else {
    mid = (l + r) / 2;
    build(i * 2, l, mid);
    build(i * 2 + 1, mid + 1, r);
    T[i].key = T[i * 2].key + T[i * 2 + 1].key;
  }
}
void release(int i, int l0, int r0) {
  int mid;
  if (l0 < r0) {
    mid = (l0 + r0) / 2;
    T[i * 2].key = T[i * 2].key + (S[mid] - S[l0 - 1]) * T[i].tag;
    T[i * 2].tag = (T[i * 2].tag + T[i].tag) % p;
    T[i * 2 + 1].key = T[i * 2 + 1].key + (S[r0] - S[mid]) * T[i].tag;
    T[i * 2 + 1].tag = (T[i * 2 + 1].tag + T[i].tag) % p;
  }
  T[i].tag = 0;
}
void modify(int i, int x, int l0, int r0, long long d) {
  int mid;
  if (l0 == r0)
    T[i].key = A[l0] * d;
  else {
    mid = (l0 + r0) / 2;
    release(i, l0, r0);
    if (x <= mid)
      modify(i * 2, x, l0, mid, d);
    else
      modify(i * 2 + 1, x, mid + 1, r0, d);
    T[i].key = T[i * 2].key + T[i * 2 + 1].key;
  }
}
void modify2(int i, int l, int r, int l0, int r0, long long d) {
  int mid;
  if ((l0 >= l) && (r0 <= r)) {
    T[i].key = T[i].key + (S[r0] - S[l0 - 1]) * d;
    T[i].tag = (T[i].tag + d) % p;
  } else {
    mid = (l0 + r0) / 2;
    release(i, l0, r0);
    if (l <= mid) modify2(i * 2, l, r, l0, mid, d);
    if (r >= mid + 1) modify2(i * 2 + 1, l, r, mid + 1, r0, d);
    T[i].key = T[i * 2].key + T[i * 2 + 1].key;
  }
}
pair<long long, long long> query(int i, int l, int r, int l0, int r0) {
  pair<long long, long long> ans;
  int mid;
  if ((l0 >= l) && (r0 <= r)) return T[i].key;
  mid = (l0 + r0) / 2;
  release(i, l0, r0);
  ans = make_pair(0, 0);
  if (l <= mid) ans = ans + query(i * 2, l, r, l0, mid);
  if (r >= mid + 1) ans = ans + query(i * 2 + 1, l, r, mid + 1, r0);
  return ans;
}
int main() {
  pair<long long, long long> B;
  long long z;
  int i, op, x, y;
  scanf("%d%d", &n, &m);
  for (i = 1; i <= n; i++) scanf("%I64d", &a[i]);
  N = 1 << int(ceil(log(n) / log(2)));
  F[0] = 1;
  F[1] = 1;
  for (i = 2; i <= N + 1; i++) F[i] = (F[i - 1] + F[i - 2]) % p;
  for (i = 0; i <= N + 1; i++)
    if (i % 2)
      G[i] = (p - F[i]) % p;
    else
      G[i] = F[i];
  for (i = 0; i <= N; i++) {
    A[i] = make_pair(F[i], F[i + 1]);
    if (i == 0)
      S[i] = A[i];
    else
      S[i] = S[i - 1] + A[i];
  }
  build(1, 1, N);
  for (i = 1; i <= m; i++) {
    scanf("%d", &op);
    switch (op) {
      case 1:
        scanf("%d%I64d", &x, &z);
        modify(1, x, 1, N, z);
        break;
      case 2:
        scanf("%d%d", &x, &y);
        B = query(1, x, y, 1, N);
        printf("%I64d\n", (B.first * G[x] + B.second * G[x - 1]) % p);
        break;
      case 3:
        scanf("%d%d%I64d", &x, &y, &z);
        modify2(1, x, y, 1, N, z);
    }
  }
  return 0;
}
