#include <bits/stdc++.h>
using namespace std;
int n, m;
long long a[200009], fab[200009];
int main() {
  fab[0] = fab[1] = 1;
  for (int i = 2; i <= 10000; i++)
    fab[i] = (fab[i - 1] + fab[i - 2]) % 1000000000;
  while (scanf("%d %d", &n, &m) == 2) {
    for (int i = 1; i <= n; i++) cin >> a[i];
    while (m--) {
      int t;
      scanf("%d", &t);
      if (t == 1) {
        long long v;
        int x;
        cin >> x >> v;
        a[x] = v;
      } else {
        int l, r;
        cin >> l >> r;
        long long sum = 0;
        for (int i = l; i <= r; i++)
          sum += fab[i - l] * (a[i]), sum %= 1000000000;
        cout << sum << endl;
      }
    }
  }
  return 0;
}
