#include <bits/stdc++.h>
using namespace std;
const int MX = 100005, INF = 1000000000, mod = 1000000000;
const long long int LINF = 1000000000000000000ll;
const double eps = 1e-9;
const int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, -1, 0, 1};
int x[MX];
int main() {
  int n, m, a, b, c, f, g;
  long long int ans;
  scanf("%d%d", &n, &m);
  for (int i = 0; i < n; i++) scanf("%d", &x[i]);
  for (int i = 0; i < m; i++) {
    scanf("%d", &a);
    if (a == 1) {
      scanf("%d%d", &a, &b);
      a--;
      x[a] = b;
    } else if (a == 2) {
      scanf("%d%d", &a, &b);
      a--;
      b--;
      f = g = 1;
      ans = 0;
      while (a <= b) {
        ans += (long long int)x[a] * f;
        ans %= mod;
        swap(f, g);
        g = (f + g) % mod;
        a++;
      }
      printf("%I64d\n", ans);
    }
  }
  return 0;
}
