#include <bits/stdc++.h>
int mod = (int)1e9;
int fibs[200010], sumfibs[200010];
int a[200010];
int n, m, N;
int sum0[4 * 200010 + 10], sum1[4 * 200010 + 10], delta[4 * 200010 + 10];
int lo[4 * 200010 + 10], hi[4 * 200010 + 10];
int ans[4 * 200010 + 10][3];
int mult(int x, int y) { return (int)((x * 1LL * y) % mod); }
int sumfib(int x) { return sumfibs[x]; }
int fib(int x) {
  if (x < 0) return 0;
  return fibs[x];
}
int advance(int f0, int f1, int k) {
  if (k == 0) return f0;
  return (mult(fib(k - 1), f1) + mult(fib(k - 2), f0)) % mod;
}
void push(int i) {
  if (delta[i] == 0) return;
  int range = hi[i] - lo[i];
  sum0[i] = (sum0[i] + mult(delta[i], sumfib(range))) % mod;
  sum1[i] =
      (sum1[i] + mult(delta[i], (sumfib(range + 1) + mod - 1) % mod)) % mod;
  if (lo[i] != hi[i]) {
    delta[i << 1] = (delta[i << 1] + delta[i]) % mod;
    delta[(i << 1) | 1] = (delta[(i << 1) | 1] + delta[i]) % mod;
  }
  delta[i] = 0;
}
void update(int i) {
  if (lo[i] != hi[i]) {
    int loRange = hi[i << 1] - lo[i << 1] + 1;
    sum0[i] = (sum0[i << 1] +
               advance(sum0[(i << 1) | 1], sum1[(i << 1) | 1], loRange)) %
              mod;
    sum1[i] = (sum1[i << 1] +
               advance(sum0[(i << 1) | 1], sum1[(i << 1) | 1], loRange + 1)) %
              mod;
  }
}
void init(int i, int L, int R) {
  lo[i] = L;
  hi[i] = R;
  delta[i] = 0;
  if (L == R) {
    sum0[i] = sum1[i] = a[L - 1];
    return;
  }
  int M = (L + R - 1) / 2;
  init(2 * i, L, M);
  init(2 * i + 1, M + 1, R);
  update(i);
}
void initTree(int L, int H) {
  N = H - L + 1;
  init(1, L, H);
}
void Zadd(int i, int L, int R, int x) {
  if (lo[i] >= L && hi[i] <= R) {
    delta[i] = (delta[i] + x) % mod;
    push(i);
    update(i);
  } else if (hi[i] >= L && lo[i] <= R) {
    push(i);
    Zadd(i << 1, L, R, x);
    Zadd((i << 1) | 1, L, R, x);
    update(i);
  }
}
void add(int L, int R, int x) { Zadd(1, L, R, x); }
void Zset(int i, int X, int v) {
  if (lo[i] == X && hi[i] == X) {
    delta[i] = 0;
    sum0[i] = sum1[i] = v;
  } else if (hi[i] >= X && lo[i] <= X) {
    push(i);
    Zset(i << 1, X, v);
    Zset((i << 1) | 1, X, v);
    update(i);
  }
}
void set(int X, int v) { Zset(1, X, v); }
void Zsum(int i, int L, int R) {
  push(i);
  update(i);
  if (lo[i] >= L && hi[i] <= R) {
    ans[i][0] = sum0[i];
    ans[i][1] = sum1[i];
    ans[i][2] = hi[i] - lo[i] + 1;
    return;
  }
  if (hi[i] < L || lo[i] > R) {
    ans[i][0] = ans[i][1] = ans[i][2] = 0;
    return;
  }
  Zsum(i << 1, L, R);
  Zsum((i << 1) | 1, L, R);
  ans[i][0] = (ans[i << 1][0] + advance(ans[(i << 1) | 1][0],
                                        ans[(i << 1) | 1][1], ans[i << 1][2])) %
              mod;
  ans[i][1] =
      (ans[i << 1][1] + advance(ans[(i << 1) | 1][0], ans[(i << 1) | 1][1],
                                ans[i << 1][2] + 1)) %
      mod;
  ans[i][2] = ans[i << 1][2] + ans[(i << 1) | 1][2];
}
int sum(int L, int R) {
  Zsum(1, L, R);
  return ans[1][0];
}
int main() {
  fibs[0] = fibs[1] = 1;
  int i, t, x, v, l, r, d;
  for (i = 2; i < 200010; i++) fibs[i] = (fibs[i - 1] + fibs[i - 2]) % mod;
  sumfibs[0] = fibs[0];
  for (i = 1; i < 200010; i++) sumfibs[i] = (sumfibs[i - 1] + fibs[i]) % mod;
  scanf("%d %d", &n, &m);
  for (i = 0; i < n; i++) scanf("%d", &a[i]);
  initTree(1, n);
  for (i = 0; i < m; i++) {
    scanf("%d", &t);
    if (t == 1) {
      scanf("%d %d", &x, &v);
      set(x, v);
    }
    if (t == 2) {
      scanf("%d %d", &l, &r);
      printf("%d\n", sum(l, r));
    }
    if (t == 3) {
      scanf("%d %d %d", &l, &r, &d);
      add(l, r, d);
    }
  }
  return 0;
}
