#include <bits/stdc++.h>
using namespace std;
struct node {
  long long f0sum, f1sum;
};
long long a[222222], fib[222222];
int get(node n, int k) {
  if (k < 0) return n.f0sum;
  if (k == 0) return n.f0sum;
  if (k == 1) return n.f1sum;
  long long ans = fib[k - 1] * n.f1sum % 1000000000;
  ans = (ans + fib[k - 2] * n.f0sum) % 1000000000;
  return ans;
}
node st[222222 << 2];
void make_tree(int cur, int s, int e) {
  if (e - s == 1) {
    st[cur].f0sum = a[s];
    st[cur].f1sum = a[s];
    return;
  }
  make_tree(cur << 1, s, (s + e) / 2);
  make_tree((cur << 1) | 1, (s + e) / 2, e);
  st[cur].f0sum =
      (st[cur << 1].f0sum + get(st[(cur << 1) + 1], (s + e) / 2 - s)) %
      1000000000;
  st[cur].f1sum =
      (st[cur << 1].f1sum + get(st[(cur << 1) + 1], (s + e) / 2 - s + 1)) %
      1000000000;
  return;
}
node query(int cur, int S, int E, int s, int e) {
  if (s >= S && e <= E) {
    return st[cur];
  }
  if (s >= E || e <= S) {
    node temp;
    temp.f0sum = temp.f1sum = 0;
    return temp;
  }
  node a = query(cur << 1, S, E, s, (s + e) / 2);
  node b = query((cur << 1) + 1, S, E, (s + e) / 2, e);
  a.f0sum = (a.f0sum + get(b, (s + e) / 2 - max(s, S))) % 1000000000;
  a.f1sum = (a.f1sum + get(b, (s + e) / 2 - max(s, S) + 1)) % 1000000000;
  return a;
}
void update(int cur, int s, int e, int wer, int val) {
  if (wer < s || wer >= e) return;
  if (e - s == 1) {
    st[cur].f0sum = st[cur].f1sum = val;
    return;
  }
  update(cur << 1, s, (s + e) / 2, wer, val);
  update((cur << 1) + 1, (s + e) / 2, e, wer, val);
  st[cur].f0sum =
      (st[cur << 1].f0sum + get(st[(cur << 1) + 1], (s + e) / 2 - s)) %
      1000000000;
  st[cur].f1sum =
      (st[cur << 1].f1sum + get(st[(cur << 1) + 1], (s + e) / 2 - s + 1)) %
      1000000000;
}
int main() {
  fib[0] = fib[1] = 1;
  for (int i = 2; i < 222222; i++)
    fib[i] = (fib[i - 1] + fib[i - 2]) % 1000000000;
  int n, m;
  cin >> n >> m;
  for (int i = 0; i < n; i++) cin >> a[i];
  make_tree(1, 0, n);
  int l, r, type;
  while (m--) {
    cin >> type;
    if (type == 1) {
      cin >> l >> r;
      update(1, 0, n, l - 1, r);
    } else {
      cin >> l >> r;
      cout << query(1, l - 1, r, 0, n).f0sum << endl;
    }
  }
  return 0;
}
