#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1000000000;
long long fib[200005];
template <class T>
class segment_tree {
 private:
  int N;
  T* tree1;
  T* tree2;
  T val(int node, int f) {
    if (f == 0)
      return tree1[node];
    else if (f == 1)
      return tree2[node];
    else
      return (fib[f - 2] * tree1[node] + fib[f - 1] * tree2[node]) % MOD;
  }
  void update(int node, int b, int e, int x, int v) {
    if (e < x || x < b)
      return;
    else if (x <= b && e <= x)
      tree1[node] = tree2[node] = v;
    else {
      update(2 * node + 0, b, (b + e) / 2, x, v);
      update(2 * node + 1, (b + e) / 2 + 1, e, x, v);
      int len = (b + e) / 2 - b + 1;
      tree1[node] = (val(2 * node, 0) + val(2 * node + 1, len)) % MOD;
      tree2[node] = (val(2 * node, 1) + val(2 * node + 1, len + 1)) % MOD;
    }
  }
  T query(int node, int b, int e, int i, int j) {
    if (e < i || j < b)
      return 0;
    else if (i <= b && e <= j)
      return val(node, b - i);
    else {
      T res = (query(2 * node + 0, b, (b + e) / 2, i, j) +
               query(2 * node + 1, (b + e) / 2 + 1, e, i, j)) %
              MOD;
      return res;
    }
  }

 public:
  segment_tree(int n) {
    N = n;
    tree1 = new T[4 * N + 1];
    tree2 = new T[4 * N + 1];
  }
  void update(int x, int v) {
    assert(1 <= x && x <= N);
    update(1, 1, N, x, v);
  }
  T query(int i, int j) {
    assert(1 <= i && i <= j && j <= N);
    return query(1, 1, N, i, j);
  }
};
int N, M;
int main() {
  scanf("%d%d", &N, &M);
  fib[0] = fib[1] = 1;
  for (int i = (int)2, _b = (int)N; i <= _b; i++)
    fib[i] = (fib[i - 1] + fib[i - 2]) % MOD;
  segment_tree<long long> st(N);
  for (int i = 0, _n = (int)N; i < _n; i++) {
    int x;
    scanf("%d", &x);
    st.update(i + 1, x);
  }
  for (int i = 0, _n = (int)M; i < _n; i++) {
    int t;
    scanf("%d", &t);
    if (t == 1) {
      int x, v;
      scanf("%d%d", &x, &v);
      st.update(x, v);
    } else {
      int l, r;
      scanf("%d%d", &l, &r);
      printf("%d\n", (int)st.query(l, r));
    }
  }
}
