#include <bits/stdc++.h>
using namespace std;
template <typename T>
T abs(T a) {
  return a < 0 ? -a : a;
}
template <typename T>
T sqr(T a) {
  return a * a;
}
const int INF = (int)1e9;
const long double EPS = 1e-9;
const long double PI = 3.1415926535897932384626433832795;
const int N = 300500;
const long long M = 1000000000;
long long f[N], fsum[N];
long long f0[N], f1[N];
long long n, m;
long long a[N];
long long trF0[4 * N];
long long trF1[4 * N];
void update(int i, long long v, int idx = 0, int lf = 0, int rg = n - 1) {
  if (lf == rg) {
    a[i] = v % M;
    trF0[idx] = a[i];
    trF1[idx] = 0;
  } else {
    int mid = (lf + rg) >> 1;
    if (i <= mid)
      update(i, v, 2 * idx + 1, lf, mid);
    else
      update(i, v, 2 * idx + 2, mid + 1, rg);
    trF0[idx] = trF0[2 * idx + 1];
    trF1[idx] = trF1[2 * idx + 1];
    int ln = (mid - lf + 1);
    trF0[idx] = (trF0[idx] + trF0[2 * idx + 2] * 1ll * f0[ln]) % M;
    trF1[idx] = (trF1[idx] + trF0[2 * idx + 2] * 1ll * f1[ln]) % M;
    trF0[idx] = (trF0[idx] + trF1[2 * idx + 2] * 1ll * f0[ln + 1]) % M;
    trF1[idx] = (trF1[idx] + trF1[2 * idx + 2] * 1ll * f1[ln + 1]) % M;
  }
}
pair<long long, long long> getSum(int qlf, int qrg, int idx = 0, int lf = 0,
                                  int rg = n - 1) {
  if (qlf == lf && qrg == rg) {
    return pair<long long, long long>(trF0[idx], trF1[idx]);
  } else {
    int mid = (lf + rg) >> 1;
    pair<long long, long long> res;
    if (qlf <= mid) {
      res = getSum(qlf, min(mid, qrg), 2 * idx + 1, lf, mid);
    }
    if (mid + 1 <= qrg) {
      pair<long long, long long> cur =
          getSum(max(mid + 1, qlf), qrg, 2 * idx + 2, mid + 1, rg);
      if (qlf <= mid) {
        int ln = mid - qlf + 1;
        res.first = (res.first + cur.first * 1ll * f0[ln]) % M;
        res.second = (res.second + cur.first * 1ll * f1[ln]) % M;
        res.first = (res.first + cur.second * 1ll * f0[ln + 1]) % M;
        res.second = (res.second + cur.second * 1ll * f1[ln + 1]) % M;
      } else {
        res = cur;
      }
    }
    return res;
  }
}
int main() {
  f[0] = f[1] = 1;
  for (int i = 2; i < N; ++i) f[i] = (f[i - 1] + f[i - 2]) % M;
  fsum[0] = f[0];
  for (int i = 1; i < N; ++i) fsum[i] = (fsum[i - 1] + f[i]) % M;
  f0[0] = 1;
  f1[0] = 0;
  f0[1] = 0;
  f1[1] = 1;
  for (int i = 2; i < N; ++i) {
    f0[i] = (f0[i - 1] + f0[i - 2]) % M;
    f1[i] = (f1[i - 1] + f1[i - 2]) % M;
  }
  cin >> n >> m;
  for (int i = 0; i < int(n); ++i) {
    scanf("%I64d", &a[i]);
    update(i, a[i]);
  }
  for (int cq = 0; cq < int(m); ++cq) {
    int t;
    scanf("%d", &t);
    if (t == 1) {
      long long x, v;
      scanf("%I64d %I64d", &x, &v);
      x--;
      update(x, v % M);
      continue;
    }
    if (t == 2) {
      long long lf, rg;
      scanf("%I64d %I64d", &lf, &rg);
      lf--;
      rg--;
      pair<long long, long long> res = getSum(lf, rg);
      long long sum = (res.first + res.second) % M;
      printf("%I64d\n", sum);
      continue;
    }
    if (t == 3) {
      throw;
      int d, lf, rg;
      scanf("%d %d %d", &lf, &rg, &d);
      lf--;
      rg--;
      for (int i = lf; i <= rg; ++i) a[i] = (a[i] + d) % M;
      continue;
    }
  }
  return 0;
}
