#include <bits/stdc++.h>
const int N = 10005, oo = 1000000000;
int a[N], f[N], n, m, type, l, r;
int main() {
  scanf("%d%d", &n, &m);
  f[0] = f[1] = 1;
  for (int i = 2; i <= n; i++) f[i] = (f[i - 1] + f[i - 2]) % oo;
  for (int i = 1; i <= n; i++) scanf("%d", a + i);
  while (m--) {
    scanf("%d%d%d", &type, &l, &r);
    if (type == 1)
      a[l] = r;
    else {
      long long ans = 0;
      for (int i = l; i <= r; i++) ans += 1LL * a[i] * f[i - l];
      printf("%d\n", ans % oo);
    }
  }
  return 0;
}
