#include <bits/stdc++.h>
int compare(const void *a, const void *b) {
  return *(long long unsigned int *)a - *(long long unsigned int *)b;
}
int main() {
  long long unsigned int arr[109], n, ar[109], m, i;
  arr[0] = 1;
  arr[1] = 1;
  for (i = 2; i <= 101; i++) {
    arr[i] = arr[i - 1] + arr[i - 2];
    if (arr[i] >= 1000000000) arr[i] -= 1000000000;
  }
  scanf("%llu", &n);
  scanf("%llu", &m);
  for (i = 0; i < n; i++) scanf("%llu", &ar[i]);
  while (m--) {
    long long unsigned int t, p, q;
    scanf("%llu", &t), scanf("%llu", &p), scanf("%llu", &q);
    if (t == 1)
      ar[p - 1] = q;
    else {
      long long unsigned int count = 0, ans = 0;
      for (i = p - 1; i < q; i++) {
        ans = ans + (ar[i] * arr[count]) % 1000000000;
        if (ans >= 1000000000) ans -= 1000000000;
        count++;
      }
      printf("%llu\n", ans);
    }
  }
  return 0;
}
