#include <bits/stdc++.h>
#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;
const int MOD = 1000000000;
int n, m, a[200005];
int f[200005] = {1};
int main() {
  f[1] = 1;
  for (int i = 2; i <= 200000; i++) f[i] = (f[i - 1] + f[i - 2]) % MOD;
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
  while (m--) {
    int k, l, r;
    scanf("%d%d%d", &k, &l, &r);
    if (k == 1) {
      a[l] = r;
    } else {
      int ans = 0;
      for (int i = l; i <= r; i++) {
        ans = ((long long)ans + (long long)f[i - l] * a[i]) % MOD;
      }
      printf("%d\n", ans);
    }
  }
}
