#include <bits/stdc++.h>
using namespace std;
const int INF = 1 << 29;
const double EPS = 1e-8;
const double PI = acos(-1);
long long f[105];
long long a[100];
const int mod = 1e9;
int main() {
  f[0] = 1;
  f[1] = 1;
  for (int i = 0; i < (int)100; ++i) f[i + 2] = (f[i + 1] + f[i]) % mod;
  int n, m;
  while (cin >> n >> m) {
    for (int i = 0; i < (int)n; ++i) cin >> a[i];
    for (int i = 0; i < (int)m; ++i) {
      int t;
      cin >> t;
      if (t == 1) {
        int x, v;
        cin >> x >> v;
        x--;
        a[x] = v;
      } else if (t == 2) {
        int l, r;
        cin >> l >> r;
        l--;
        r--;
        long long ans = 0;
        for (int i = 0; i < (int)r - l + 1; ++i) {
          ans = (ans + f[i] * a[l + i]) % mod;
        }
        cout << ans << endl;
      } else {
        int l, r, d;
        cin >> l >> r >> d;
        l--;
        r--;
        for (int i = l; i <= r; ++i) a[i] += d;
      }
    }
  }
}
