#include <bits/stdc++.h>
using namespace std;
const int MOD = 1000000000;
const int N = 1000100;
int node[2][N], l[N], h[N];
int n, m, a[N], add[N];
long long f[N];
int fx(int r, int i) {
  if (i == 0) return node[0][r];
  int x = node[0][r], y = node[1][r];
  return (f[i - 1] * x % MOD + f[i] * node[1][r] % MOD) % MOD;
}
void Merge(int r) {
  node[0][r] = (node[0][r * 2] + fx(r * 2 + 1, h[r * 2] - l[r * 2] + 1)) % MOD;
  node[1][r] = (node[1][r * 2] + fx(r * 2 + 1, h[r * 2] - l[r * 2] + 2)) % MOD;
}
void build(int r, int low, int high) {
  l[r] = low;
  h[r] = high;
  if (low == high) {
    node[0][r] = node[1][r] = a[low];
    return;
  }
  int mid = (low + high) / 2;
  build(r * 2, low, mid);
  build(r * 2 + 1, mid + 1, high);
  Merge(r);
}
void fy(int r, int d) {
  add[r] = (add[r] + d) % MOD;
  int len = h[r] - l[r] + 1;
  int res1 = (long long)(f[len + 2] - 1) * d % MOD;
  int res2 = (long long)(f[len + 3] - 2) * d % MOD;
  node[0][r] = (node[0][r] + res1) % MOD;
  node[1][r] = (node[1][r] + res2) % MOD;
}
void down(int r) {
  if (l[r] == h[r]) return;
  fy(r * 2, add[r]);
  fy(r * 2 + 1, add[r]);
  add[r] = 0;
}
void modify_one(int r, int low, int high, int value) {
  if (l[r] > high || h[r] < low) return;
  if (l[r] >= low && h[r] <= high) {
    node[0][r] = node[1][r] = value;
    return;
  }
  down(r);
  modify_one(r * 2, low, high, value);
  modify_one(r * 2 + 1, low, high, value);
  Merge(r);
}
int calc(int r, int low, int high) {
  if (l[r] > high || h[r] < low) return 0;
  if (l[r] >= low && h[r] <= high) return fx(r, l[r] - low);
  down(r);
  int ans = (calc(r * 2, low, high) + calc(r * 2 + 1, low, high)) % MOD;
  Merge(r);
  return ans;
}
void modify_range(int r, int low, int high, int d) {
  if (l[r] > high || h[r] < low) return;
  if (l[r] >= low && h[r] <= high) {
    fy(r, d);
    return;
  }
  down(r);
  modify_range(r * 2, low, high, d);
  modify_range(r * 2 + 1, low, high, d);
  Merge(r);
}
int main() {
  cin >> n >> m;
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
  f[1] = 1;
  for (int i = 2; i <= n + 5; i++) f[i] = (f[i - 1] + f[i - 2]) % MOD;
  build(1, 1, n);
  for (int i = 1; i <= m; i++) {
    int t, l, r;
    scanf("%d%d%d", &t, &l, &r);
    if (t == 1)
      modify_one(1, l, l, r);
    else if (t == 2)
      printf("%d\n", calc(1, l, r));
    else {
      scanf("%d", &t);
      modify_range(1, l, r, t);
    }
  }
}
