#include <bits/stdc++.h>
using namespace std;
const int maxn = 210005;
const int SIZE = 1111111;
const int mod = 1000000000;
const long long INF = 0x7f7f7f7f7f7f7f7fLL;
const double eps = 1e-10;
int f[maxn], a[maxn];
unsigned long long s[maxn << 2][2];
int len[maxn << 2];
void pushup(int rt) {
  static int L, R;
  L = rt << 1;
  R = rt << 1 | 1;
  int k = len[L];
  s[rt][0] = s[L][0];
  s[rt][1] = s[L][1];
  s[rt][1] += (s[R][0] * f[k - 1] + s[R][1] * f[k]);
  s[rt][1] %= mod;
  if (k > 1) {
    s[rt][0] += (s[R][0] * f[k - 2] + s[R][1] * f[k - 1]);
  } else {
    s[rt][0] += (s[R][1]);
  }
  s[rt][0] %= mod;
}
void build(int l, int r, int rt) {
  len[rt] = r - l + 1;
  if (l == r) {
    s[rt][0] = s[rt][1] = a[l];
    return;
  }
  int m = (l + r) >> 1;
  build(l, m, rt << 1);
  build(m + 1, r, rt << 1 | 1);
  pushup(rt);
}
long long query(int L, int R, int l, int r, int rt) {
  if (L <= l && r <= R) {
    int k = l - L;
    if (k == 0) return s[rt][0];
    if (k == 1) return s[rt][1];
    long long res = s[rt][0] * f[k - 2] + s[rt][1] * f[k - 1];
    return res % mod;
  }
  int m = (l + r) >> 1;
  long long ans = 0;
  if (m >= L) ans += query(L, R, l, m, rt << 1);
  if (m < R) ans += query(L, R, m + 1, r, rt << 1 | 1);
  if (ans >= mod) ans -= mod;
  return ans;
}
void update(int p, int v, int l, int r, int rt) {
  if (l == r) {
    s[rt][0] = s[rt][1] = v;
    return;
  }
  int m = (l + r) >> 1;
  if (p <= m)
    update(p, v, l, m, rt << 1);
  else
    update(p, v, m + 1, r, rt << 1 | 1);
  pushup(rt);
}
int main() {
  int i, n, l, r, t, p, v, m;
  f[0] = f[1] = 1;
  for (i = 2; i <= 200005; ++i) {
    p = f[i - 1] + f[i - 2];
    f[i] = p % mod;
  }
  scanf("%d%d", &n, &m);
  for (i = 1; i <= n; ++i) scanf("%d", a + i);
  build(1, n, 1);
  while (m--) {
    scanf("%d", &t);
    if (t == 1) {
      scanf("%d%d", &p, &v);
      update(p, v, 1, n, 1);
    } else {
      scanf("%d%d", &l, &r);
      v = (int)query(l, r, 1, n, 1);
      printf("%d\n", v);
    }
  }
  return 0;
}
