#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1000000000;
pair<long long, long long> fib[200010];
pair<long long, long long> fib_sum[200010];
const int MAX_N = 200000;
int n, dif[4 * MAX_N], sum0[4 * MAX_N], sum1[4 * MAX_N];
void init(int n_) {
  for (n = 1; n < n_; n *= 2)
    ;
  memset(dif, 0, sizeof(dif));
  memset(sum0, 0, sizeof(sum0));
  memset(sum1, 0, sizeof(sum1));
}
pair<int, int> query_sum(int a, int b, int k = 0, int l = 0, int r = 0) {
  if (k == 0) r = n;
  if (r <= a || b <= l) return make_pair(0, 0);
  pair<long long, long long> fs = make_pair(
      (fib_sum[min(r, b) - a].first - fib_sum[max(0, l - a)].first) % MOD,
      (fib_sum[min(r, b) - a].second - fib_sum[max(0, l - a)].second) % MOD);
  pair<long long, long long> sd =
      make_pair((dif[k] * fs.first) % MOD, (dif[k] * fs.second) % MOD);
  if (a <= l && r <= b) {
    pair<long long, long long> f0 = fib[l - a];
    pair<long long, long long> f1 = fib[l - a + 1];
    pair<long long, long long> v =
        make_pair((f0.first * sum0[k] + f1.first * sum1[k]) % MOD,
                  (f0.second * sum0[k] + f1.second * sum1[k]) % MOD);
    return make_pair((sd.first + v.first) % MOD, (sd.second + v.second) % MOD);
  } else {
    pair<long long, long long> vl = query_sum(a, b, k * 2 + 1, l, (l + r) / 2);
    pair<long long, long long> vr = query_sum(a, b, k * 2 + 2, (l + r) / 2, r);
    return make_pair((sd.first + vl.first + vr.first) % MOD,
                     (sd.second + vl.second + vr.second) % MOD);
  }
}
void query_add(int a, int b, int v, int k = 0, int l = 0, int r = 0) {
  if (k == 0) r = n;
  if (r <= a || b <= l) {
  } else if (a <= l && r <= b) {
    dif[k] += v;
  } else {
    query_add(a, b, v, k * 2 + 1, l, (l + r) / 2);
    query_add(a, b, v, k * 2 + 2, (l + r) / 2, r);
    pair<long long, long long> vl = query_sum(l, r, k * 2 + 1, l, (l + r) / 2);
    pair<long long, long long> vr = query_sum(l, r, k * 2 + 2, (l + r) / 2, r);
    sum0[k] = (vl.first + vr.first) % MOD;
    sum1[k] = (vl.second + vr.second) % MOD;
  }
}
int query_sum_outer(int a, int b) {
  pair<long long, long long> r = query_sum(a, b);
  return (r.first + r.second) % MOD;
}
int N, Q, A[200010];
int main() {
  while (2 == scanf("%d%d", &N, &Q)) {
    fib[0] = make_pair(1, 0);
    fib[1] = make_pair(0, 1);
    for (int i = 2; i <= N; ++i) {
      fib[i] = make_pair((fib[i - 2].first + fib[i - 1].first) % MOD,
                         (fib[i - 2].second + fib[i - 1].second) % MOD);
    }
    fib_sum[0] = make_pair(0, 0);
    for (int i = 1; i <= N; ++i) {
      fib_sum[i] = make_pair((fib_sum[i - 1].first + fib[i - 1].first) % MOD,
                             (fib_sum[i - 1].second + fib[i - 1].second) % MOD);
    }
    init(N);
    for (int i = 0; i < (int)(N); i++) {
      scanf("%d", &A[i]);
      query_add(i, i + 1, A[i]);
    }
    for (int q = 0; q < (int)(Q); q++) {
      int t;
      scanf("%d", &t);
      if (t == 1) {
        int x, v;
        scanf("%d%d", &x, &v);
        --x;
        int d = +v - query_sum_outer(x, x + 1);
        query_add(x, x + 1, d);
        A[x] = v;
      } else if (t == 2) {
        int l, r;
        scanf("%d%d", &l, &r);
        --l;
        printf("%d\n", int((query_sum_outer(l, r) + MOD) % MOD));
      } else if (t == 3) {
        int l, r, d;
        scanf("%d%d%d", &l, &r, &d);
        --l;
        query_add(l, r, d);
      }
    }
  }
  return 0;
}
