#include <bits/stdc++.h>
using namespace std;
int main(void) {
  int f[105] = {0}, n, m1, m, i, l, r, a[105], x, v;
  scanf("%d%d", &n, &m1);
  long long s = 0;
  f[0] = f[1] = 1;
  for (i = 2; i <= 105; i++) f[i] = (f[i - 1] + f[i - 2]) % 1000000000;
  for (i = 1; i <= n; i++) scanf("%d", &a[i]);
  while (m1--) {
    scanf("%d", &m);
    if (m == 1) {
      scanf("%d%d", &x, &v);
      a[x] = v;
    } else {
      s = 0;
      scanf("%d%d", &l, &r);
      for (i = 0; i <= (r - l); i++) {
        s += (long long)f[i] * a[l + i];
        s %= 1000000000;
      }
      printf("%I64d\n", s);
    }
  }
  return 0;
}
