#include <bits/stdc++.h>
#pragma comment(linker, "/STACK:102400000,102400000")
using namespace std;
const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, 1, 0, -1};
const double eps = 1e-8;
const double pi = acos(-1.0);
const int inf = 0x7f7f7f7f;
const long long llinf = 0x7f7f7f7f7f7f7f7fll;
const int mod = 1000000000;
const int maxn = 111;
template <class T>
inline bool checkmax(T &a, const T &b) {
  if (a == -1 || a < b) {
    a = b;
    return true;
  }
  return false;
}
template <class T>
inline bool checkmin(T &a, const T *b) {
  if (a == -1 || a > b) {
    a = b;
    return true;
  }
  return false;
}
long long a[maxn], fib[maxn];
int main() {
  fib[0] = fib[1] = 1;
  for (int i = 2; i < maxn; i++) {
    fib[i] = (fib[i - 1] + fib[i - 2]) % mod;
  }
  int n, m;
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) {
    scanf("%I64d", &a[i]);
  }
  while (m--) {
    int t;
    scanf("%d", &t);
    if (t == 1) {
      int first, v;
      scanf("%d%d", &first, &v);
      a[first] = v;
    } else if (t == 2) {
      int l, r;
      scanf("%d%d", &l, &r);
      long long ans = 0;
      for (int i = l; i <= r; i++) {
        ans += a[i] * fib[i - l] % mod;
        ans %= mod;
      }
      printf("%I64d\n", ans);
    } else {
      int l, r, d;
      scanf("%d%d%d", &l, &r, &d);
      for (int i = l; i <= r; i++) {
        a[i] = (a[i] + d) % mod;
      }
    }
  }
}
