#include <bits/stdc++.h>
using namespace std;
const int N = 200010;
const int mod = 1e9;
long long a[N], f[N];
int n, m;
void fib() {
  f[0] = 1;
  f[1] = 1;
  for (int i = 2; i <= n; i++) f[i] = (f[i - 1] + f[i - 2]) % mod;
}
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) scanf("%lld", &a[i]);
  fib();
  for (int i = 1; i <= m; i++) {
    int oo;
    scanf("%d", &oo);
    if (oo == 1) {
      int t;
      long long x;
      scanf("%d%lld", &t, &x);
      a[t] = x;
    } else if (oo == 2) {
      int l, r;
      scanf("%d%d", &l, &r);
      long long ans = 0;
      for (int i = l; i <= r; i++) {
        (ans += (f[i - l] * a[i]) % mod) %= mod;
      }
      printf("%lld\n", ans);
    } else {
      int l, r;
      long long x;
      scanf("%d%d%lld", &l, &r, &x);
      for (int i = l; i <= r; i++) a[i] += x;
    }
  }
}
