#include <bits/stdc++.h>
using namespace std;
long long a[202020];
long long f[202020];
int n, m;
namespace force {
void main() {
  while (m--) {
    int op;
    scanf("%d", &op);
    if (op == 1) {
      int x, v;
      scanf("%d %d", &x, &v);
      a[x] = v;
    } else if (op == 2) {
      int l, r;
      scanf("%d %d", &l, &r);
      long long ans = 0;
      for (int i = 0; i <= r - l; i++)
        (ans += ((f[i] * a[i + l] % 1000000000) + 1000000000) % 1000000000) %=
            1000000000;
      printf("%I64d\n", (ans + 1000000000) % 1000000000);
    } else {
      int l, r, d;
      scanf("%d %d %d", &l, &r, &d);
      for (int i = l; i <= r; i++) a[i] += d;
    }
  }
}
}  // namespace force
namespace more {
long long coef[202020][2];
long long sum[202020][2];
long long value[202020];
void precalc() {
  coef[0][0] = coef[1][1] = 1;
  coef[0][1] = coef[1][0] = 0;
  for (int i = 2; i <= n; i++)
    for (int j = 0; j < 2; j++)
      coef[i][j] =
          ((coef[i - 2][j] - coef[i - 1][j]) % 1000000000 + 1000000000) %
          1000000000;
}
void update(int x, int v) {
  int dt = (v - value[x]);
  value[x] = v;
  for (int r = x; r <= n; r += r & -r) {
    sum[r][0] =
        ((sum[r][0] + (long long)dt * f[x - 1]) % 1000000000 + 1000000000) %
        1000000000;
    sum[r][1] = ((sum[r][1] + (long long)dt * f[x]) % 1000000000 + 1000000000) %
                1000000000;
  }
}
long long query(int x, int flag) {
  long long ret = 0;
  for (int r = x; r; r -= r & -r)
    (ret += sum[r][flag] % 1000000000 + 1000000000) %= 1000000000;
  return ret;
}
void main() {
  memset(value, 0, sizeof(value));
  memset(sum, 0, sizeof(sum));
  precalc();
  for (int i = 1; i <= n; i++) update(i, a[i]);
  while (m--) {
    int op;
    scanf("%d", &op);
    if (op == 1) {
      int x, v;
      scanf("%d %d", &x, &v);
      update(x, v);
    } else if (op == 2) {
      int l, r;
      scanf("%d %d", &l, &r);
      long long q0 =
          ((query(r, 1) - query(l - 1, 1)) % 1000000000 + 1000000000) %
          1000000000;
      long long q1 =
          ((query(r, 0) - query(l - 1, 0)) % 1000000000 + 1000000000) %
          1000000000;
      printf("%I64d\n",
             ((q0 * coef[l][0] + q1 * coef[l][1]) % 1000000000 + 1000000000) %
                 1000000000);
    }
  }
}
}  // namespace more
int main() {
  scanf("%d %d", &n, &m);
  for (int i = 1; i <= n; i++) scanf("%I64d", &a[i]);
  f[0] = f[1] = 1;
  for (int i = 2; i <= n; i++) f[i] = (f[i - 1] + f[i - 2]) % 1000000000;
  if (n <= 100 && m <= 10000)
    force::main();
  else
    more::main();
  return 0;
}
