#include <bits/stdc++.h>
using namespace std;
inline int Get() {
  int res = 0, q = 1;
  char ch = getchar();
  while ((ch < '0' || ch > '9') && ch != '-') ch = getchar();
  if (ch == '-') q = -1, ch = getchar();
  while (ch >= '0' && ch <= '9') res = res * 10 + ch - '0', ch = getchar();
  return res * q;
}
const double eps = 1e-12, pi = M_PI;
const int oo = (int)2e9, mod = (int)1e9;
const long long INF = (long long)1e17;
const int N = (int)2e5, M = N << 2;
typedef long long arrn[N + 10];
typedef long long arrm[M + 10];
long long n, m, j, k, p, tp, ans;
arrm s[2], ad, len;
arrn a, f, fs;
long long Up(long long x, long long y) {
  return ((long long)f[y] * (long long)s[0][x] +
          (long long)f[y + 1] * (long long)s[1][x]) %
         mod;
}
void Update(long long x) {
  s[0][x] = (s[0][x << 1] + Up(x << 1 | 1, len[x << 1] - 1)) % mod;
  s[1][x] = (s[1][x << 1] + Up(x << 1 | 1, len[x << 1])) % mod;
}
void Build(long long l, long long r, long long x) {
  if (l == r) {
    s[1][x] = a[l], len[x] = 1;
    return;
  }
  long long mid = (l + r) >> 1;
  Build(l, mid, x << 1), Build(mid + 1, r, x << 1 | 1);
  len[x] = r - l + 1;
  Update(x);
}
void Add(long long x, long long dt) {
  s[0][x] = (s[0][x] + (long long)dt * (long long)fs[len[x] - 1]) % mod;
  s[1][x] = (s[1][x] + (long long)dt * (long long)fs[len[x]]) % mod;
  ad[x] += dt;
}
void Push(long long x) {
  if (ad[x]) Add(x << 1, ad[x]), Add(x << 1 | 1, ad[x]), ad[x] = 0;
}
void Change(long long l, long long r, long long x, long long pos,
            long long dt) {
  if (l == r) {
    s[1][x] = dt;
    return;
  }
  Push(x);
  long long mid = (l + r) >> 1;
  if (pos <= mid)
    Change(l, mid, x << 1, pos, dt);
  else
    Change(mid + 1, r, x << 1 | 1, pos, dt);
  Update(x);
}
void Query(long long l, long long r, long long x, long long ml, long long mr) {
  if (l >= ml && r <= mr) {
    ans = (ans + Up(x, l - ml)) % mod;
    return;
  }
  Push(x);
  long long mid = (l + r) >> 1;
  if (ml <= mid) Query(l, mid, x << 1, ml, mr);
  if (mr > mid) Query(mid + 1, r, x << 1 | 1, ml, mr);
  Update(x);
}
void Modify(long long l, long long r, long long x, long long ml, long long mr,
            long long dt) {
  if (l >= ml && r <= mr) {
    Add(x, dt);
    return;
  }
  Push(x);
  long long mid = (l + r) >> 1;
  if (ml <= mid) Modify(l, mid, x << 1, ml, mr, dt);
  if (mr > mid) Modify(mid + 1, r, x << 1 | 1, ml, mr, dt);
  Update(x);
}
int main() {
  ((n) = Get()), ((m) = Get());
  for (long long i = (1), end = (n); i <= end; ++i) {
    if (i > 1)
      f[i] = (f[i - 1] + f[i - 2]) % mod;
    else
      f[i] = 1;
    fs[i] = (fs[i - 1] + f[i]) % mod;
    ((a[i]) = Get());
  }
  Build(1, n, 1);
  for (; m--;) {
    ((tp) = Get());
    if (tp == 1) {
      ((j) = Get()), ((k) = Get());
      Change(1, n, 1, j, k);
    } else if (tp == 2) {
      ((j) = Get()), ((k) = Get()), ans = 0;
      Query(1, n, 1, j, k);
      printf(
          "%I64d"
          "\n",
          ans < 0 ? ans + mod : ans);
    } else {
      ((j) = Get()), ((k) = Get()), ((p) = Get());
      Modify(1, n, 1, j, k, p);
    }
  }
  return 0;
}
