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