#include <bits/stdc++.h>
using namespace std;
int const mod = 1000000000;
int arr[200010], i, n, m, x, y, t, z;
long long f[200010], r;
int main() {
  f[0] = f[1] = 1;
  for (i = 2; i < 200010; i++) f[i] = (f[i - 1] + f[i - 2]) % mod;
  scanf("%d%d", &n, &m);
  for (i = 1; i <= n; i++) scanf("%d", &arr[i]);
  for (i = 0; i < m; i++) {
    scanf("%d%d%d", &t, &x, &y);
    if (t == 2) {
      for (z = r = 0; z <= y - x; z++) r = (r + f[z] * arr[x + z]) % mod;
      printf("%I64d\n", r);
    } else
      arr[x] = y;
  }
  return 0;
}
