#include <bits/stdc++.h>
using namespace std;
const double PI = acos(-1.0);
int toInt(string s) {
  int r = 0;
  istringstream sin(s);
  sin >> r;
  return r;
}
long long toInt64(string s) {
  long long r = 0;
  istringstream sin(s);
  sin >> r;
  return r;
}
double toDouble(string s) {
  double r = 0;
  istringstream sin(s);
  sin >> r;
  return r;
}
double dist(double x1, double y1, double x2, double y2) {
  return sqrt(((x1 - x2) * (x1 - x2)) + ((y1 - y2) * (y1 - y2)));
}
bool isUpperCase(char c) { return c >= 'A' && c <= 'Z'; }
bool isLowerCase(char c) { return c >= 'a' && c <= 'z'; }
bool isLetter(char c) { return c >= 'A' && c <= 'Z' || c >= 'a' && c <= 'z'; }
bool isDigit(char c) { return c >= '0' && c <= '9'; }
char toLowerCase(char c) { return (isUpperCase(c)) ? (c + 32) : c; }
char toUpperCase(char c) { return (isLowerCase(c)) ? (c - 32) : c; }
template <class T>
inline T strTo(string s) {
  istringstream is(s);
  T v;
  is >> v;
  return v;
}
template <class T>
inline string toStr(const T& v) {
  ostringstream os;
  os << v;
  return os.str();
}
template <class T>
inline int cMin(T& a, const T& b) {
  return b < a ? a = b, 1 : 0;
}
template <class T>
inline int cMax(T& a, const T& b) {
  return a < b ? a = b, 1 : 0;
}
template <class T>
inline int cBit(T n) {
  return n ? cBit(n & (n - 1)) + 1 : 0;
}
template <class T>
inline T lowbit(T n) {
  return (n ^ (n - 1)) & n;
}
template <class T>
inline T GCD(T a, T b) {
  if (a < 0) return GCD(-a, b);
  if (b < 0) return GCD(a, -b);
  return (b == 0) ? a : GCD(b, a % b);
}
template <class T>
inline T LCM(T a, T b) {
  if (a < 0) return LCM(-a, b);
  if (b < 0) return LCM(a, -b);
  return a * (b / gcd(a, b));
}
const int N = 100005;
long long a[N];
int n, m;
long long f[N];
int main() {
  while (cin >> n >> m) {
    for (int i = 1; i <= n; i++) cin >> a[i];
    int t;
    long long x, v, l, r;
    for (int i = 0; i < m; i++) {
      cin >> t;
      if (t == 1) {
        cin >> x >> v;
        a[x] = v;
      } else {
        cin >> l >> r;
        f[0] = 1;
        f[1] = 1;
        long long s = 0;
        for (int i = 0; i <= r - l; i++) {
          if (i > 1) {
            f[i] = f[i - 1] + f[i - 2];
            f[i] %= 1000000000;
          }
          s += (f[i] * a[i + l]) % 1000000000;
          s %= 1000000000;
        }
        cout << s << endl;
      }
    }
  }
  return 0;
}
