#include <bits/stdc++.h>
using namespace std;
const long long inf = 1000000000;
long long a[110], f[110];
int main() {
  f[0] = f[1] = 1;
  for (int i = 2; i <= 105; ++i) f[i] = (f[i - 1] + f[i - 2]) % inf;
  int n, m, k, u, v, d;
  cin >> n >> m;
  for (int i = 1; i <= n; ++i) cin >> a[i];
  while (m--) {
    cin >> k >> u >> v;
    if (k == 1)
      a[u] = v;
    else if (k == 2) {
      long long sum = 0;
      for (int i = u, j = 0; i <= v; ++i, ++j) sum = (sum + a[i] * f[j]) % inf;
      cout << sum << endl;
    } else {
      cin >> d;
      for (int i = u; i <= v; ++i) a[i] = (a[i] + d) % inf;
    }
  }
  return 0;
}
