#include <bits/stdc++.h>
using namespace std;
const long long maxn = 2 * 100000 + 10, maxm = 5 * 1000000 + 10;
long long n, m, a[maxn], cnt, MOD = 1000000000, fib[maxm];
long long seg1[maxm], seg2[maxm];
inline long long f(long long a, long long b, long long n) {
  if (n == 0) return a;
  if (n == 1) return b;
  return (a * fib[n - 2] + b * fib[n - 1]) % MOD;
}
void init(long long node, long long st, long long en) {
  if (st == en) {
    seg1[node] = seg2[node] = a[st];
    return;
  }
  long long mid = (st + en) / 2;
  init(node * 2, st, mid);
  init(node * 2 + 1, mid + 1, en);
  long long cur1, cur2;
  cur1 = seg1[node * 2 + 1];
  cur2 = seg2[node * 2 + 1];
  seg1[node] = (seg1[node * 2] + f(cur1, cur2, mid + 1 - st)) % MOD;
  seg2[node] = (seg2[node * 2] + f(cur1, cur2, mid + 2 - st)) % MOD;
}
void add(long long node, long long st, long long en, long long x, long long v) {
  if (st == en) {
    seg1[node] += v;
    seg2[node] += v;
    seg1[node] %= MOD;
    seg2[node] %= MOD;
    return;
  }
  long long mid = (st + en) / 2;
  (seg1[node] += f(1, 1, x - st) * v % MOD) %= MOD;
  (seg2[node] += f(1, 1, x - st + 1) * v % MOD) %= MOD;
  while (seg1[node] < 0) seg1[node] += MOD;
  while (seg2[node] < 0) seg2[node] += MOD;
  if (x <= mid)
    add(node * 2, st, mid, x, v);
  else
    add(node * 2 + 1, mid + 1, en, x, v);
}
long long sum(long long node, long long st, long long en, long long l,
              long long r, long long p) {
  if (l == st && en == r) return f(seg1[node], seg2[node], p);
  long long mid = (st + en) / 2;
  if (r <= mid) return sum(node * 2, st, mid, l, r, p);
  if (l > mid) return sum(node * 2 + 1, mid + 1, en, l, r, p);
  long long ret = 0;
  ret += sum(node * 2, st, mid, l, mid, p);
  ret += sum(node * 2 + 1, mid + 1, en, mid + 1, r, mid + 1 - l + p);
  ret %= MOD;
  return ret;
}
int main() {
  fib[0] = fib[1] = 1;
  for (int i = 2; i < maxm; i++) fib[i] = (fib[i - 1] + fib[i - 2]) % MOD;
  ios_base::sync_with_stdio(false);
  cin >> n >> m;
  for (long long i = 0; i < n; i++) cin >> a[i];
  init(1, 0, n - 1);
  for (long long i = 0; i < m; i++) {
    long long t;
    cin >> t;
    if (t == 1) {
      long long x, v;
      cin >> x >> v;
      x--;
      add(1, 0, n - 1, x, v - a[x]);
      a[x] = v;
    } else {
      long long l, r;
      cin >> l >> r;
      l--;
      r--;
      cout << sum(1, 0, n - 1, l, r, 0) << '\n';
    }
  }
  return 0;
}
