#include <bits/stdc++.h>
using namespace std;
int n, t[2][200011], val[200011], fib[200011];
int mod(long long a, int m = 1000000000) { return (a % m + m) % m; }
struct Matrix {
  int v[2][2];
  Matrix() { memset(v, 0, sizeof(v)); }
};
Matrix mul(Matrix a, Matrix b) {
  Matrix c;
  int i, j, k;
  for (i = 0; i < 2; i++)
    for (j = 0; j < 2; j++)
      for (k = 0; k < 2; k++)
        c.v[i][j] = mod(c.v[i][j] + 1ll * a.v[i][k] * b.v[k][j]);
  return c;
}
Matrix exp(Matrix m, int e) {
  if (e == 1) return m;
  if (e % 2 == 0) return exp(mul(m, m), e / 2);
  return mul(m, exp(m, e - 1));
}
void update(int i, int v) {
  int r = i, delta;
  delta = mod(v - val[i]);
  val[i] = v;
  for (; r <= n; r += r & -r) {
    t[0][r] = mod(t[0][r] + 1ll * delta * fib[i - 1]);
    t[1][r] = mod(t[1][r] + 1ll * delta * fib[i]);
  }
}
int query(int i, int s) {
  int ret = 0, r = i;
  for (; r; r -= r & -r) ret = mod(ret + t[s][r]);
  return ret;
}
int find(int a, int b, int n) {
  Matrix M;
  M.v[0][1] = 1;
  M.v[1][0] = 1;
  M.v[1][1] = -1;
  M = exp(M, n);
  return mod(1ll * a * M.v[0][0] + 1ll * b * M.v[1][0]);
}
int main() {
  int m, a, i, t, x, v, l, r, q0, q1;
  cin >> n >> m;
  fib[0] = fib[1] = 1;
  for (i = 2; i <= n; i++) fib[i] = mod(fib[i - 1] + fib[i - 2]);
  for (i = 1; i <= n; i++) {
    cin >> a;
    update(i, a);
  }
  while (m--) {
    cin >> t;
    if (t == 1) {
      cin >> x >> v;
      update(x, v);
    }
    if (t == 2) {
      cin >> l >> r;
      q0 = mod(query(r, 0) - query(l - 1, 0));
      q1 = mod(query(r, 1) - query(l - 1, 1));
      cout << find(q1, q0, l) << endl;
    }
  }
  return 0;
}
