#include <bits/stdc++.h>
using namespace std;
long long f[1000];
int a[1000];
int n, m;
void fibo() {
  f[0] = 1, f[1] = 1;
  int i, j, k;
  for (i = 2; i <= 1005; i++) f[i] = (f[i - 1] + f[i - 2]) % 1000000000;
}
int main() {
  int tc, cs;
  int i, j, k;
  fibo();
  cin >> n >> m;
  for (i = 1; i <= n; i++) cin >> a[i];
  for (k = 1; k <= m; k++) {
    int t;
    cin >> t;
    if (t == 1) {
      int x, y;
      cin >> x >> y;
      a[x] = y;
    } else if (t == 2) {
      int x, y;
      cin >> x >> y;
      long long sum = 0;
      for (i = x; i <= y; i++) {
        sum = sum + (f[i - x] * a[i]);
      }
      cout << sum % 1000000000 << endl;
    }
  }
  return 0;
}
