#include <bits/stdc++.h>
using namespace std;
const long long Mod = 1000000000;
const int N = 200010;
long long d[N];
long long f[N];
long long mat[2][2] = {{0, 1}, {1, -1}};
long long sum0[N], sum1[N];
int lowbit(int x) { return x & (-x); }
void add(long long a[N], int k, long long val) {
  while (k < N) {
    a[k] += val;
    a[k] %= Mod;
    k += lowbit(k);
  }
}
long long sum(long long a[N], int k) {
  long long res = 0;
  while (k) {
    res += a[k];
    res %= Mod;
    k -= lowbit(k);
  }
  return res;
}
void matX(long long a[2][2], long long b[2][2], long long c[2][2]) {
  long long res[2][2];
  memset(res, 0, sizeof(res));
  for (int i = 0; i < 2; ++i)
    for (int j = 0; j < 2; ++j)
      for (int k = 0; k < 2; ++k) res[i][j] += (a[i][k] * b[k][j]) % Mod;
  for (int i = 0; i < 2; ++i)
    for (int j = 0; j < 2; ++j) c[i][j] = res[i][j] % Mod;
}
long long mat_multi(int k, long long Tip, long long Ti) {
  long long res[2][2];
  memset(res, 0, sizeof(res));
  res[0][0] = res[1][1] = 1;
  long long base[2][2];
  for (int i = 0; i < 2; ++i)
    for (int j = 0; j < 2; ++j) base[i][j] = mat[i][j];
  while (k) {
    if (k & 1) matX(base, res, res);
    k >>= 1;
    matX(base, base, base);
  }
  long long r = res[1][0] * Tip + res[1][1] * Ti;
  return (r + Mod) % Mod;
}
void init() {
  f[0] = f[1] = 1;
  for (int i = 2; i < N; ++i) f[i] = (f[i - 1] + f[i - 2]) % Mod;
}
int main() {
  ios_base::sync_with_stdio(false);
  init();
  int n, m;
  cin >> n >> m;
  for (int i = 1; i <= n; ++i) cin >> d[i];
  sum0[0] = sum1[0] = 0;
  for (int i = 1; i <= n; ++i) {
    add(sum0, i, d[i] * f[i - 1]);
    add(sum1, i, d[i] * f[i]);
  }
  while (m--) {
    int t;
    cin >> t;
    if (t == 1) {
      int x, v;
      cin >> x >> v;
      long long cur = sum(sum0, x) - sum(sum0, x - 1);
      add(sum0, x, f[x - 1] * v - cur);
      cur = sum(sum1, x) - sum(sum1, x - 1);
      add(sum1, x, f[x] * v - cur);
    } else if (t == 2) {
      int l, r;
      cin >> l >> r;
      long long Ti = sum(sum1, r) - sum(sum1, l - 1);
      long long Ti_1 = sum(sum0, r) - sum(sum0, l - 1);
      long long res = mat_multi(l - 1, Ti, Ti_1);
      cout << (res + Mod) % Mod << endl;
    }
  }
  return 0;
}
