#include <bits/stdc++.h>
using namespace std;
const long long MAX = 2e5 + 9, MOD = 1e9;
pair<int, int> seg[4 * MAX];
int n, m, x, lazy[4 * MAX], fib[MAX], pfib[MAX];
pair<int, int> merge(pair<int, int> a, pair<int, int> b, int l, int mid) {
  pair<int, int> ans;
  if (mid - l == 1) {
    ans.first = (a.first + b.second) % MOD,
    ans.second = (1LL * a.second + b.first + b.second) % MOD;
    return ans;
  }
  ans.first = (1LL * a.first + 1LL * fib[mid - l - 2] * b.first +
               1LL * fib[mid - l - 1] * b.second) %
              MOD,
  ans.second = (1LL * a.second + 1LL * fib[mid - l - 1] * b.first +
                1LL * fib[mid - l] * b.second) %
               MOD;
  return ans;
}
void update(int v, int l, int r, int val) {
  lazy[v] = (lazy[v] + val) % MOD;
  seg[v].first = (1LL * seg[v].first + 1LL * pfib[r - l - 1] * val) % MOD;
  seg[v].second =
      (1LL * seg[v].second + 1LL * (pfib[r - l] - pfib[0]) * val) % MOD;
}
void shift(int v, int l, int r) {
  int mid = (l + r) / 2;
  update(2 * v, l, mid, lazy[v]), update(2 * v + 1, mid, r, lazy[v]);
  lazy[v] = 0;
}
void add(int v, int l, int r, int s, int e, int val) {
  if (e <= l || s >= r) return;
  if (s <= l && e >= r) {
    update(v, l, r, val);
    return;
  }
  int mid = (l + r) / 2;
  shift(v, l, r);
  add(2 * v, l, mid, s, e, val), add(2 * v + 1, mid, r, s, e, val);
  seg[v] = merge(seg[2 * v], seg[2 * v + 1], l, mid);
}
pair<int, int> get(int v, int l, int r, int s, int e) {
  if (s <= l && e >= r) return seg[v];
  int mid = (l + r) / 2;
  shift(v, l, r);
  if (e <= mid)
    return get(2 * v, l, mid, s, e);
  else if (s >= mid)
    return get(2 * v + 1, mid, r, s, e);
  else
    return merge(get(2 * v, l, mid, s, mid), get(2 * v + 1, mid, r, mid, e), s,
                 mid);
}
int main() {
  ios_base::sync_with_stdio(0), cin.tie(0);
  cin >> n >> m;
  fib[0] = fib[1] = pfib[0] = 1;
  for (int i = 2; i < n; i++) fib[i] = (fib[i - 1] + fib[i - 2]) % MOD;
  for (int i = 1; i < n; i++) pfib[i] = (pfib[i - 1] + fib[i]) % MOD;
  for (int i = 0; i < n; i++) cin >> x, add(1, 0, n, i, i + 1, x);
  for (int i = 0; i < m; i++) {
    int c, x, y, d;
    cin >> c >> x >> y, x--;
    if (c == 1) add(1, 0, n, x, x + 1, y - get(1, 0, n, x, x + 1).first);
    if (c == 2) cout << get(1, 0, n, x, y).first << '\n';
    if (c == 3) cin >> d, add(1, 0, n, x, y, d);
  }
  return 0;
}
