#include <bits/stdc++.h>
using namespace std;
const long long maxn = 2 * 100 * 1000 + 10;
const long long mod = 1000 * 1000 * 1000;
long long a[maxn];
long long sum[maxn * 8 + 1][2], ff1[maxn], ff2[maxn], f[maxn], all[maxn * 8];
long long n, m;
long long sumff1[maxn], sumff2[maxn];
inline long long GetSum1(long long fi, long long se) {
  long long ret = sumff1[se] - sumff1[fi] + ff1[fi];
  ret %= mod;
  if (ret < 0) ret += mod;
  return ret;
}
inline long long GetSum2(long long fi, long long se) {
  long long ret = sumff2[se] - sumff2[fi] + ff2[fi];
  ret %= mod;
  if (ret < 0) ret += mod;
  return ret;
}
inline void Add(long long fi, long long se, long long val, long long beg,
                long long end, long long ind) {
  if (fi == beg && se == end) {
    val += all[ind];
    val %= mod;
    all[ind] = 0;
    all[ind * 2] += val;
    all[ind * 2 + 1] += val;
    all[ind * 2] %= mod;
    all[ind * 2 + 1] %= mod;
    sum[ind][0] += sumff1[end - beg] * val;
    sum[ind][1] += sumff2[end - beg] * val;
    sum[ind][0] %= mod;
    sum[ind][1] %= mod;
    if (sum[ind][0] < 0) sum[ind][0] += mod;
    if (sum[ind][1] < 0) sum[ind][1] += mod;
    return;
  }
  Add(beg, end, 0, beg, end, ind);
  long long mid = (beg + end) / 2;
  if (fi <= mid) Add(fi, min(se, mid), val, beg, mid, ind * 2);
  if (se > mid) Add(max(fi, mid + 1), se, val, mid + 1, end, ind * 2 + 1);
  sum[ind][0] += val * GetSum1(fi - beg, se - beg);
  sum[ind][1] += val * GetSum2(fi - beg, se - beg);
  sum[ind][0] %= mod;
  sum[ind][1] %= mod;
  if (sum[ind][0] < 0) sum[ind][0] += mod;
  if (sum[ind][1] < 0) sum[ind][1] += mod;
}
inline long long GetSum(long long fi, long long se, long long beg,
                        long long end, long long ind, long long f1) {
  if (fi == beg && se == end) {
    long long ret = sum[ind][0] * f[f1] % mod;
    ret += sum[ind][1] * f[f1 + 1] % mod;
    ret %= mod;
    return ret;
  }
  long long ret = 0;
  long long mid = (beg + end) / 2;
  if (fi <= mid) ret += GetSum(fi, min(se, mid), beg, mid, ind * 2, f1);
  if (se > mid) {
    if (fi > mid)
      ret += GetSum(fi, se, mid + 1, end, ind * 2 + 1, f1);
    else
      ret += GetSum(mid + 1, se, mid + 1, end, ind * 2 + 1, f1 + mid + 1 - fi);
  }
  ret %= mod;
  return ret;
}
int main() {
  ios_base::sync_with_stdio(false);
  f[0] = f[1] = 1;
  for (long long i = 2; i < maxn; ++i) f[i] = (f[i - 1] + f[i - 2]) % mod;
  ff1[0] = 1;
  ff1[1] = 0;
  for (long long i = 2; i < maxn; ++i) ff1[i] = (ff1[i - 1] + ff1[i - 2]) % mod;
  ff2[0] = 0;
  ff2[1] = 1;
  for (long long i = 2; i < maxn; ++i) ff2[i] = (ff2[i - 1] + ff2[i - 2]) % mod;
  sumff1[0] = ff1[0];
  for (long long i = 1; i < maxn; ++i)
    sumff1[i] = (ff1[i] + sumff1[i - 1]) % mod;
  sumff2[0] = ff2[0];
  for (long long i = 1; i < maxn; ++i)
    sumff2[i] = (ff2[i] + sumff2[i - 1]) % mod;
  cin >> n >> m;
  for (long long i = 1; i <= n; ++i) {
    long long cp;
    cin >> cp;
    cp %= mod;
    Add(i, i, cp, 1, n, 1);
  }
  for (long long qw = 0; qw < m; ++qw) {
    long long fi, se, th;
    cin >> fi >> se >> th;
    if (fi == 1) {
      th %= mod;
      Add(se, se, 0, 1, n, 1);
      long long sss = GetSum(se, se, 1, n, 1, 0);
      sss = -sss + th;
      sss %= mod;
      if (sss < 0) sss += mod;
      Add(se, se, sss, 1, n, 1);
    } else if (fi == 2) {
      long long sum = 0;
      long long n1 = 1, n2 = 1;
      Add(se, th, 0, 1, n, 1);
      cout << GetSum(se, th, 1, n, 1, 0) << "\n";
    }
    if (fi == 3) {
      long long fo;
      cin >> fo;
      Add(se, th, fo, 1, n, 1);
    }
  }
  return 0;
}
