#include <bits/stdc++.h>
using namespace std;
const int maxn = 2 * 100000 + 10;
const long long mod = 1000 * 1000 * 1000;
long long a[maxn];
long long sum[maxn * 4][2], ff1[maxn], ff2[maxn], f[maxn];
int n, m;
inline long long GetSum(int fi, int se, int beg, int end, int ind, int 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;
  int 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;
}
inline void Change(int id, int val, int beg, int end, int ind) {
  if (beg == end) {
    sum[ind][0] = val;
    sum[ind][1] = 0;
    return;
  }
  int mid = (beg + end) / 2;
  if (id <= mid)
    Change(id, val, beg, mid, ind * 2);
  else
    Change(id, val, mid + 1, end, ind * 2 + 1);
  sum[ind][0] += (val - a[id]) * ff1[id - beg];
  sum[ind][1] += (val - a[id]) * ff2[id - 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;
}
int main() {
  ios_base::sync_with_stdio(false);
  f[0] = f[1] = 1;
  for (int i = 2; i < maxn; ++i) f[i] = (f[i - 1] + f[i - 2]) % mod;
  ff1[0] = 1;
  ff1[1] = 0;
  for (int i = 2; i < maxn; ++i) ff1[i] = (ff1[i - 1] + ff1[i - 2]) % mod;
  ff2[0] = 0;
  ff2[1] = 1;
  for (int i = 2; i < maxn; ++i) ff2[i] = (ff2[i - 1] + ff2[i - 2]) % mod;
  cin >> n >> m;
  for (int i = 1; i <= n; ++i) {
    int cp;
    cin >> cp;
    Change(i, cp, 1, n, 1);
    a[i] = cp;
  }
  for (int qw = 0; qw < m; ++qw) {
    int fi, se, th;
    cin >> fi >> se >> th;
    if (fi == 1) {
      Change(se, th % mod, 1, n, 1);
      a[se] = th % mod;
    } else if (fi == 2) {
      long long sum = 0;
      long long n1 = 1, n2 = 1;
      cout << GetSum(se, th, 1, n, 1, 0) << endl;
    }
  }
  return 0;
}
