#include <bits/stdc++.h>
using namespace std;
char arr[50000000], *ptr;
long long ret;
string str;
inline long long get_int() {
  bool isNeg = false;
  ret = 0;
  while (!((*ptr >= '0' && *ptr <= '9') || *ptr == '-')) ptr++;
  while ((*ptr >= '0' && *ptr <= '9') || *ptr == '-') {
    if (*ptr == '-')
      isNeg = true;
    else
      ret = ret * 10 + (*ptr - '0');
    ptr++;
  }
  if (isNeg) ret = -ret;
  return ret;
}
class BIT {
 public:
  long long tree[200005];
  BIT() { memset(tree, 0, sizeof(tree)); }
  int read(int idx) {
    int sum = 0;
    while (idx > 0) {
      sum += tree[idx];
      sum = sum % 1000000000;
      idx -= (idx & -idx);
    }
    return sum;
  }
  void update(int idx, int val) {
    while (idx <= 200005) {
      tree[idx] += val;
      tree[idx] = tree[idx] % 1000000000;
      idx += (idx & -idx);
    }
  }
  int rsq(int from_value, int to_value) {
    return (read(to_value) - read(from_value - 1));
  }
} bit;
int a[200005];
long long fib[200005];
long long n, m;
long long ans[200005];
void genFib() {
  fib[0] = 1;
  fib[1] = 1;
  for (int i = 2; i < 200002; i++) {
    fib[i] = (fib[i - 1] + fib[i - 2]) % 1000000000;
  }
}
int main() {
  fread(arr, sizeof(char), 50000000, stdin);
  ptr = arr;
  int t;
  long long l, r, x, v, d;
  n = get_int();
  m = get_int();
  for (int i = 1; i <= n; i++) a[i] = get_int();
  genFib();
  for (int i = 0; i < m; i++) {
    t = get_int();
    if (t == 1) {
      x = get_int();
      v = get_int();
      a[x] = v;
    } else if (t == 2) {
      l = get_int();
      r = get_int();
      long long ans = 0;
      for (int i = 0; i <= (r - l); i++) {
        ans += (fib[i] * a[l + i]) % 1000000000;
        ans %= 1000000000;
      }
      cout << ans << endl;
    } else {
      l = get_int();
      r = get_int();
      d = get_int();
    }
  }
  return 0;
}
