#include <bits/stdc++.h>
using namespace std;
const int INF = 2147483647;
const int MOD = 1000000000;
const int N = 600000;
int fib[N], fibA[N], fibB[N], tab[N], w[N], zmA[N], zmB[N], x, v, a, b, n, m, t,
    i, M, lewa[N], prawa[N];
void insert(int x, int v) {
  int s = M + x, zm;
  while (s) {
    zm = (fib[x - lewa[s]] * 1LL * abs(v)) % MOD;
    if (v > 0)
      w[s] = (w[s] + zm) % MOD;
    else
      w[s] = (w[s] + MOD - zm) % MOD;
    zm = (fibA[x - lewa[s]] * 1LL * abs(v)) % MOD;
    if (v > 0)
      zmA[s] = (zmA[s] + zm) % MOD;
    else
      zmA[s] = (zmA[s] + MOD - zm) % MOD;
    zm = (fibB[x - lewa[s]] * 1LL * abs(v)) % MOD;
    if (v > 0)
      zmB[s] = (zmB[s] + zm) % MOD;
    else
      zmB[s] = (zmB[s] + MOD - zm) % MOD;
    s /= 2;
  }
}
int query(int a, int b, int c, int d = 1) {
  if (lewa[d] > b || prawa[d] < a) return 0;
  if (lewa[d] == a && prawa[d] == b)
    return (fib[c] * 1LL * zmA[d] + fib[c + 1] * 1LL * zmB[d]) % MOD;
  int przes = max(a, lewa[2 * d + 1]) - a;
  return (query(a, min(b, prawa[2 * d]), c, 2 * d) +
          query(max(a, lewa[2 * d + 1]), b, c + przes, 2 * d + 1)) %
         MOD;
}
void init(int a) {
  M = 1;
  while (M < a) M *= 2;
  int i, j;
  for (i = M; i < 2 * M; i++) {
    w[i] = tab[i - M + 1];
    zmA[i] = w[i];
    zmB[i] = 0;
    lewa[i] = prawa[i] = i - M + 1;
  }
  for (i = M - 1; i >= 1; i--) {
    lewa[i] = lewa[2 * i];
    prawa[i] = prawa[2 * i + 1];
    w[i] = zmA[i] = zmB[i] = 0;
    for (j = lewa[i]; j <= prawa[i]; j++) {
      w[i] = (fib[j - lewa[i]] * 1LL * tab[j] + w[i]) % MOD;
      zmA[i] = (fibA[j - lewa[i]] * 1LL * tab[j] + zmA[i]) % MOD;
      zmB[i] = (fibB[j - lewa[i]] * 1LL * tab[j] + zmB[i]) % MOD;
    }
  }
  M--;
}
int main() {
  fib[0] = fib[1] = 1;
  for (i = 2; i < N; i++) fib[i] = (fib[i - 2] + fib[i - 1]) % MOD;
  fibA[0] = 1;
  fibA[1] = 0;
  fibB[0] = 0;
  fibB[1] = 1;
  for (i = 2; i < N; i++) fibA[i] = (fibA[i - 2] + fibA[i - 1]) % MOD;
  for (i = 2; i < N; i++) fibB[i] = (fibB[i - 2] + fibB[i - 1]) % MOD;
  scanf("%d %d", &n, &m);
  for (i = 1; i <= n; i++) scanf("%d", &tab[i]);
  init(n);
  while (m--) {
    scanf("%d", &t);
    if (t == 1) {
      scanf("%d %d", &x, &v);
      insert(x, v - tab[x]);
      tab[x] = v;
    } else if (t == 2) {
      scanf("%d %d", &a, &b);
      printf("%d\n", query(a, b, 0));
    }
  }
  return 0;
}
