#include <bits/stdc++.h>
using namespace std;
template <class T>
T fm(T number, T module) {
  T result = 1;
  while (number > 1) {
    result = (result * ((number / module) % 2 ? module - 1 : 1)) % module;
    for (T it = 2; it <= (number % module); ++it) {
      result = (result * it) % module;
    }
    number /= module;
  }
  return result % module;
}
int main(int argc, char *argv[]) {
  std::ios_base::sync_with_stdio(false);
  vector<long long> fibb(101, 0);
  fibb[0] = 1;
  fibb[1] = 1;
  for (unsigned it(2); it != 101; ++it) {
    fibb[it] = (fibb[it - 1] + fibb[it - 2]) % 1000000000LL;
  }
  unsigned n(0), k(0);
  cin >> n >> k;
  vector<long long> array(n, 0);
  for (unsigned it(0); it != n; ++it) {
    cin >> array[it];
  }
  for (unsigned it(0); it != k; ++it) {
    unsigned type(0);
    cin >> type;
    if (type == 1) {
      long long left, right;
      cin >> left >> right;
      --left;
      array[left] = right;
    } else if (type == 2) {
      long long left, right;
      cin >> left >> right;
      long long answer(0);
      for (unsigned il(0); il <= (right - left); ++il) {
        answer += fibb[il] * array[left + il - 1];
      }
      cout << (answer % 1000000000LL) << endl;
    }
  }
  return 0;
}
