#include <bits/stdc++.h>
#pragma comment(linker, "/STACK:200000000")
using namespace std;
template <typename T>
inline T Abs(T x) {
  return (x >= 0) ? x : -x;
}
template <typename T>
inline T sqr(T x) {
  return x * x;
}
template <typename T>
inline string toStr(T x) {
  stringstream st;
  st << x;
  string s;
  st >> s;
  return s;
}
template <typename T>
inline int bit(T mask, int b) {
  return (b >= 0 && (mask & (T(1) << b)) != 0) ? 1 : 0;
}
inline int nextInt() {
  int x;
  if (scanf("%d", &x) != 1) throw;
  return x;
}
inline long long nextInt64() {
  long long x;
  if (scanf("%I64d", &x) != 1) throw;
  return x;
}
inline double nextDouble() {
  double x;
  if (scanf("%lf", &x) != 1) throw;
  return x;
}
const int INF = (int)1E9;
const long long INF64 = (long long)1E18;
const long double EPS = 1E-9;
const long double PI = 3.1415926535897932384626433832795;
const int MAXN = 300100;
const int MOD = INF;
long long a[MAXN], f[MAXN];
int n, m;
void update(int x, int value) { a[x] = value; }
int query(int l, int r) {
  long long ans = 0;
  for (int i = l; i <= r; i++) ans = (ans + f[i - l] * a[i]) % MOD;
  return int(ans % MOD);
}
int main() {
  f[0] = f[1] = 1;
  for (int i = 2; i < MAXN; i++) f[i] = (f[i - 1] + f[i - 2]) % MOD;
  n = nextInt();
  m = nextInt();
  for (int i = 0; i < (int)(n); i++) a[i] = nextInt();
  for (int q = 0; q < (int)(m); q++) {
    int type = nextInt();
    if (type == 1) {
      int x = nextInt() - 1;
      int value = nextInt();
      update(x, value);
    }
    if (type == 2) {
      int l = nextInt() - 1;
      int r = nextInt() - 1;
      printf("%d\n", query(l, r));
    }
    if (type == 3) {
      int l = nextInt() - 1;
      int r = nextInt() - 1;
      int x = nextInt();
    }
  }
  return 0;
}
