#include <bits/stdc++.h>
using namespace std;
long long f[200005], s[200005];
struct seg {
  int x, y, l, d;
  seg() { d = 0; }
  void set(int _x, int _y, int _l) { x = _x, y = _y, l = _l; }
  void renew(int dd) {
    d = (d + dd) % 1000000000, x = (x + s[l] * dd) % 1000000000,
    y = (y + s[l - 1] * dd) % 1000000000;
  }
} t[200005 * 4];
int N, M, a[200005];
void init() {
  scanf("%d%d", &N, &M), f[1] = s[1] = 1;
  for (int i = 1; i <= N; i++)
    scanf("%d", &a[i]), f[i + 1] = (f[i] + f[i - 1]) % 1000000000,
                              s[i + 1] = (s[i] + f[i + 1]) % 1000000000;
}
seg update(const seg& A, const seg& B) {
  seg C;
  C.l = A.l + B.l;
  C.x = (A.x + f[A.l + 1] * B.x + f[A.l] * B.y) % 1000000000;
  C.y = (A.y + f[A.l] * B.x + f[A.l - 1] * B.y) % 1000000000;
  return C;
}
void build(int p, int L, int R) {
  if (L == R) {
    t[p].set(a[L], 0, 1);
    return;
  }
  build((p << 1), L, ((L + R) >> 1)),
      build(((p << 1) + 1), ((L + R) >> 1) + 1, R),
      t[p] = update(t[(p << 1)], t[((p << 1) + 1)]);
}
void change(int p, int L, int R, int x, int v) {
  if (L == R) {
    t[p].set(v, 0, 1);
    return;
  }
  if (t[p].d)
    t[(p << 1)].renew(t[p].d), t[((p << 1) + 1)].renew(t[p].d), t[p].d = 0;
  if (x <= ((L + R) >> 1))
    change((p << 1), L, ((L + R) >> 1), x, v);
  else
    change(((p << 1) + 1), ((L + R) >> 1) + 1, R, x, v);
  t[p] = update(t[(p << 1)], t[((p << 1) + 1)]);
}
void add(int p, int L, int R, int l, int r, int d) {
  if (l <= L && R <= r) {
    t[p].renew(d);
    return;
  }
  if (t[p].d)
    t[(p << 1)].renew(t[p].d), t[((p << 1) + 1)].renew(t[p].d), t[p].d = 0;
  if (r <= ((L + R) >> 1))
    add((p << 1), L, ((L + R) >> 1), l, r, d);
  else if (((L + R) >> 1) < l)
    add(((p << 1) + 1), ((L + R) >> 1) + 1, R, l, r, d);
  else
    add((p << 1), L, ((L + R) >> 1), l, ((L + R) >> 1), d),
        add(((p << 1) + 1), ((L + R) >> 1) + 1, R, ((L + R) >> 1) + 1, r, d);
  t[p] = update(t[(p << 1)], t[((p << 1) + 1)]);
}
seg calc(int p, int L, int R, int l, int r) {
  if (l <= L && R <= r) return t[p];
  if (t[p].d)
    t[(p << 1)].renew(t[p].d), t[((p << 1) + 1)].renew(t[p].d), t[p].d = 0;
  if (r <= ((L + R) >> 1))
    return calc((p << 1), L, ((L + R) >> 1), l, r);
  else if (((L + R) >> 1) < l)
    return calc(((p << 1) + 1), ((L + R) >> 1) + 1, R, l, r);
  else
    return update(
        calc((p << 1), L, ((L + R) >> 1), l, ((L + R) >> 1)),
        calc(((p << 1) + 1), ((L + R) >> 1) + 1, R, ((L + R) >> 1) + 1, r));
}
void doit() {
  build(1, 1, N);
  for (int i = 1, t, l, r, d; i <= M; i++) {
    scanf("%d%d%d", &t, &l, &r);
    if (t == 1)
      change(1, 1, N, l, r);
    else if (t == 2)
      printf("%d\n", calc(1, 1, N, l, r).x);
    else
      scanf("%d", &d), add(1, 1, N, l, r, d);
  }
}
int main() {
  init();
  doit();
  return 0;
}
