#include <bits/stdc++.h>
using namespace std;
long long N, Q;
long long A[200005], F[200005];
int main() {
  F[0] = F[1] = 1;
  for (int i = 2; i < 200005; i++) F[i] = (F[i - 1] + F[i - 2]) % 1000000000;
  cin >> N >> Q;
  for (int i = 1; i <= N; i++) cin >> A[i];
  for (int i = 0; i < Q; i++) {
    int t;
    cin >> t;
    if (t == 1) {
      int x;
      long long v;
      cin >> x >> v;
      A[x] = v;
    }
    if (t == 2) {
      long long l, r;
      cin >> l >> r;
      long long sum = 0;
      for (int x = 0; l + x <= r; x++) {
        sum += F[x] * A[x + l];
        sum %= 1000000000;
      }
      cout << sum << "\n";
    }
  }
}
