#include <bits/stdc++.h>
long long int F[1001];
void DP() {
  F[0] = F[1] = 1;
  for (int k = 2; k < 1001; k++) F[k] = ((F[k - 1] + F[k - 2]) % 1000000000);
  return;
}
int main(void) {
  DP();
  long long int n, m, s = 0, A[1001], x, t, v;
  scanf("%lld%lld", &n, &m);
  for (int k = 1; k <= n; k++) scanf("%lld", &A[k]);
  while (m > 0) {
    scanf("%lld%lld%lld", &t, &x, &v);
    if (t == 1) A[x] = v;
    if (t == 2) {
      s = 0;
      for (int i = x; i <= v; ++i) {
        s += (A[i] * F[i - x]);
        s %= 1000000000;
      }
      printf("%lld\n", s);
    }
    m--;
  }
  return 0;
}
