#include <bits/stdc++.h>
const double pi = acos(-1.0);
using namespace std;
int a[212345];
int main() {
  int module = 1000000000;
  int n, m;
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
  for (int i = 0; i < m; ++i) {
    int temp;
    scanf("%d", &temp);
    if (temp == 1) {
      int pl, v;
      scanf("%d %d", &pl, &v);
      a[pl] = v;
    }
    if (temp == 2) {
      int le, ri, f0 = 1, f1 = 1;
      scanf("%d %d", &le, &ri);
      int ans = 0;
      for (int x = 0; x <= ri - le; ++x) {
        int f;
        if (x < 2)
          f = 1;
        else {
          f = (f1 + f0) % module;
          f0 = f1;
          f1 = f;
        }
        ans = (ans + ((long long)a[le + x] * f) % module) % module;
      }
      printf("%d\n", ans);
    }
  }
  return 0;
}
