#include <bits/stdc++.h>
using namespace std;
template <class T>
bool umin(T& a, T b) {
  if (a > b) {
    a = b;
    return 1;
  }
  return 0;
}
template <class T>
bool umax(T& a, T b) {
  if (a < b) {
    a = b;
    return 1;
  }
  return 0;
}
int arr[200009], f[200009];
int mod(long long x) { return (x % 1000000000); }
struct node {
  int n0, n1;
} s[200009 << 2], temp;
node merge(int len, node x, node y) {
  if (!len) return y;
  node z = x;
  z.n0 =
      mod(z.n0 + mod(mod(y.n0 * 1LL * f[len - 1]) + mod(y.n1 * 1LL * f[len])));
  z.n1 =
      mod(z.n1 + mod(mod(y.n0 * 1LL * f[len]) + mod(y.n1 * 1LL * f[len + 1])));
  return z;
}
void build(int nd, int x, int y) {
  if (x == y) {
    s[nd].n0 = arr[x];
    s[nd].n1 = arr[x];
    return;
  }
  int mid = (x + y) >> 1;
  build(nd << 1, x, mid);
  build(nd << 1 | 1, mid + 1, y);
  s[nd] = merge(mid - x + 1, s[nd << 1], s[nd << 1 | 1]);
}
void upd(int p, int v, int nd, int x, int y) {
  if (x == y) {
    s[nd].n0 = v;
    s[nd].n1 = v;
    return;
  }
  int mid = (x + y) >> 1;
  if (p <= mid)
    upd(p, v, nd << 1, x, mid);
  else
    upd(p, v, nd << 1 | 1, mid + 1, y);
  s[nd] = merge(mid - x + 1, s[nd << 1], s[nd << 1 | 1]);
}
void tap(int l, int r, int nd, int x, int y) {
  if (l > y or x > r) return;
  if (l <= x and y <= r) {
    temp = merge(x - l, temp, s[nd]);
    return;
  }
  int mid = (x + y) >> 1;
  tap(l, r, nd << 1, x, mid);
  tap(l, r, nd << 1 | 1, mid + 1, y);
}
int main() {
  f[1] = f[2] = 1;
  for (int i = 3; i < 200009; i++) f[i] = mod(f[i - 1] + f[i - 2]);
  int n, q;
  scanf("%d%d", &n, &q);
  for (int i = 1; i <= n; i++) scanf("%d", &arr[i]);
  build(1, 1, n);
  while (q--) {
    int type;
    scanf("%d", &type);
    if (type == 1) {
      int v, p;
      scanf("%d%d", &p, &v);
      upd(p, v, 1, 1, n);
    }
    if (type == 2) {
      int l, r;
      scanf("%d%d", &l, &r);
      tap(l, r, 1, 1, n);
      printf("%d\n", temp.n0);
    }
  }
  return 0;
}
