#include <bits/stdc++.h>
template <class T>
T _diff(T a, T b) {
  return (a < b ? b - a : a - b);
}
template <class T>
T _abs(T a) {
  return (a < 0 ? -a : a);
}
template <class T>
T _max(T a, T b) {
  return (a > b ? a : b);
}
template <class T>
T _min(T a, T b) {
  return (a < b ? a : b);
}
template <class T>
T max3(T a, T b, T c) {
  return (_max(a, b) > c ? _max(a, b) : c);
}
template <class T>
T min3(T a, T b, T c) {
  return (_min(a, b) < c ? _min(a, b) : c);
}
template <class T>
T GCD(T a, T b) {
  a = _abs(a);
  b = _abs(b);
  T tmp;
  while (a % b) {
    tmp = a % b;
    a = b;
    b = tmp;
  }
  return b;
}
template <class T>
T LCM(T a, T b) {
  a = _abs(a);
  b = _abs(b);
  return (a / GCD(a, b)) * b;
}
using namespace std;
long long fab[105], a[105], res, v;
int n, i, m, x, t, s;
int main() {
  fab[0] = fab[1] = 1;
  for (i = 2; i < 101; i++) fab[i] = (fab[i - 1] + fab[i - 2]) % 1000000000;
  cin >> n >> m;
  for (i = 1; i <= n; i++) cin >> a[i];
  while (m--) {
    scanf("%d", &t);
    if (t == 1) {
      cin >> x >> v;
      a[x] = v;
    } else {
      cin >> s >> x;
      res = 0;
      for (i = s; i <= x; i++)
        res = (res + (fab[i - s] * a[i]) % 1000000000) % 1000000000;
      cout << res << endl;
    }
  }
  return 0;
}
