#include <bits/stdc++.h>
using namespace std;
long long pre[105], s[105];
int n, m;
int main() {
  pre[0] = 1;
  pre[1] = 1;
  for (int i = (2); i <= (100); i++)
    pre[i] = (pre[i - 1] + pre[i - 2]) % 1000000000;
  scanf("%d %d", &n, &m);
  for (int i = (1); i <= (n); i++) scanf("%lld", &s[i]);
  for (int i = (1); i <= (m); i++) {
    int a, b, c;
    scanf("%d %d %d", &a, &b, &c);
    if (a == 1) {
      s[b] = c;
    } else {
      long long ans = 0;
      for (int j = (b); j <= (c); j++)
        ans = (ans + pre[j - b] * s[j]) % 1000000000;
      printf("%lld\n", ans);
    }
  }
  return 0;
}
