#include <bits/stdc++.h>
using namespace std;
long long n, m;
long long a[110];
long long f[110];
long long mod = 1e9;
void fib() {
  f[0] = f[1] = 1;
  for (long long i = 2; i <= n; i++)
    f[i] = ((f[i - 1] % mod) + (f[i - 2] % mod)) % mod;
}
int main() {
  cin >> n >> m;
  fib();
  for (long long i = 1; i <= n; i++) cin >> a[i];
  while (m--) {
    long long t;
    cin >> t;
    t--;
    if (t) {
      long long l, r;
      cin >> l >> r;
      long long ans = 0;
      for (long long i = l, j = 0; i <= r; i++, j++)
        ans = (ans + ((f[j] % mod) * (a[i] % mod)) % mod) % mod;
      cout << ans % mod << '\n';
    } else {
      long long x, b;
      cin >> x >> b;
      a[x] = b;
    }
  }
  return 0;
}
