#include <bits/stdc++.h>
using namespace std;
const long long T = 300055;
long long AA, BB, d, was, i, l, r, j, t, v, x, N, M;
long long sum[T], B[T], F[T], A[T];
struct node {
  long long l, r, sum0, sum1, save;
};
node g[8 * T];
void build(long long a, long long b, long long u) {
  g[u] = (node){a, b, 0ll, 0ll, 0ll};
  if (a == b) return;
  long long mid = (a + b) >> 1;
  build(a, mid, 2 * u);
  build(mid + 1, b, 2 * u + 1);
}
void update(long long pos, long long delta, long long u) {
  long long left = g[u].l;
  long long right = g[u].r;
  if (g[u].save) {
    AA = left;
    BB = right;
    g[u].sum0 = (g[u].sum0 +
                 (long long)g[u].save * (sum[BB - left + 1] - sum[AA - left]) %
                     1000000000 +
                 1000000000) %
                1000000000;
    g[u].sum1 =
        (g[u].sum1 +
         (long long)g[u].save * (sum[BB - left + 1 + 1] - sum[AA - left + 1]) %
             1000000000 +
         1000000000) %
        1000000000;
    g[2 * u].save += g[u].save;
    g[2 * u + 1].save += g[u].save;
    g[u].save = 0;
  }
  if (pos < left || right < pos) return;
  if (left == right) {
    g[u].sum0 = g[u].sum1 = delta % 1000000000;
    return;
  }
  update(pos, delta, 2 * u);
  update(pos, delta, 2 * u + 1);
  g[u].sum0 =
      (long long)((long long)g[u].sum0 +
                  (long long)(delta - was) * (F[pos - left]) % 1000000000 +
                  (long long)1000000000 + (long long)1000000000) %
      1000000000;
  g[u].sum1 =
      (long long)((long long)g[u].sum1 +
                  (long long)(delta - was) * (F[pos - left + 1]) % 1000000000 +
                  (long long)1000000000 + (long long)1000000000) %
      1000000000;
}
long long get(long long s0, long long s1, long long num) {
  if (num == 0) return s0;
  if (num == 1) return s1;
  num--;
  return (long long)((long long)s0 * F[num - 1] % 1000000000 +
                     (long long)s1 * F[num] % 1000000000) %
         1000000000;
}
long long go(long long a, long long b, long long u) {
  long long left = g[u].l;
  long long right = g[u].r;
  if (g[u].save) {
    AA = left;
    BB = right;
    g[u].sum0 =
        (g[u].sum0 +
         (long long)g[u].save *
             (sum[BB - left + 1] - sum[AA - left] + 1000000000) % 1000000000 +
         1000000000) %
        1000000000;
    g[u].sum1 =
        (g[u].sum1 +
         (long long)g[u].save *
             (sum[BB - left + 1 + 1] - sum[AA - left + 1] + 1000000000) %
             1000000000 +
         1000000000) %
        1000000000;
    g[2 * u].save += g[u].save;
    g[2 * u + 1].save += g[u].save;
    g[u].save = 0;
  }
  if (left > b || a > right) return 0;
  if (a <= left && right <= b) {
    return get(g[u].sum0, g[u].sum1, left - a);
  }
  return ((long long)go(a, b, 2 * u) + go(a, b, 2 * u + 1)) % 1000000000;
}
void godown(long long a, long long b, long long delta, long long u) {
  long long left = g[u].l;
  long long right = g[u].r;
  if (g[u].save) {
    AA = left;
    BB = right;
    g[u].sum0 =
        (g[u].sum0 +
         (long long)g[u].save *
             (sum[BB - left + 1] - sum[AA - left] + 1000000000) % 1000000000 +
         1000000000) %
        1000000000;
    g[u].sum1 =
        (g[u].sum1 +
         (long long)g[u].save *
             (sum[BB - left + 1 + 1] - sum[AA - left + 1] + 1000000000) %
             1000000000 +
         1000000000) %
        1000000000;
    g[2 * u].save += g[u].save;
    g[2 * u + 1].save += g[u].save;
    g[u].save = 0;
  }
  if (a > right || left > b) return;
  AA = max(a, left);
  BB = min(b, right);
  g[u].sum0 =
      (g[u].sum0 +
       (long long)delta * (sum[BB - left + 1] - sum[AA - left] + 1000000000) %
           1000000000 +
       1000000000) %
      1000000000;
  g[u].sum1 = (g[u].sum1 +
               (long long)delta *
                   (sum[BB - left + 1 + 1] - sum[AA - left + 1] + 1000000000) %
                   1000000000 +
               1000000000) %
              1000000000;
  if (a <= left && right <= b) {
    g[2 * u].save += delta;
    g[2 * u + 1].save += delta;
    return;
  }
  godown(a, b, delta, 2 * u);
  godown(a, b, delta, 2 * u + 1);
}
struct pode {
  long long l, r, num, save;
};
pode G[8 * T];
void buildd(long long a, long long b, long long u) {
  G[u] = (pode){a, b, 0, 0};
  if (a == b) return;
  long long mid = (a + b) >> 1;
  buildd(a, mid, 2 * u);
  buildd(mid + 1, b, 2 * u + 1);
}
long long gett(long long pos, long long u) {
  long long left = G[u].l;
  long long right = G[u].r;
  if (G[u].save) {
    G[u].num += G[u].save;
    G[2 * u].save += G[u].save;
    G[2 * u + 1].save += G[u].save;
    G[u].save = 0;
  }
  if (pos < left || right < pos) return 0;
  if (left == right) return G[u].num;
  return gett(pos, 2 * u) + gett(pos, 2 * u + 1);
}
void updatee(long long a, long long b, long long delta, long long u) {
  long long left = G[u].l;
  long long right = G[u].r;
  if (a > right || left > b) return;
  if (a <= left && right <= b) {
    G[u].num += delta;
    G[2 * u].save += delta;
    G[2 * u + 1].save += delta;
    return;
  }
  updatee(a, b, delta, 2 * u);
  updatee(a, b, delta, 2 * u + 1);
}
int main() {
  F[0] = F[1] = 1;
  for (i = 2; i <= 200005; i++)
    F[i] = ((long long)F[i - 1] + F[i - 2]) % 1000000000;
  for (i = 1; i <= 200005; i++) sum[i] = (sum[i - 1] + F[i - 1]) % 1000000000;
  scanf("%I64d %I64d", &N, &M);
  buildd(1, N, 1);
  build(1, N, 1);
  for (i = 1; i <= N; i++)
    scanf("%I64d", &A[i]), update(i, A[i], 1), updatee(i, i, A[i], 1);
  while (M--) {
    scanf("%I64d", &t);
    if (t == 1) {
      scanf("%I64d %I64d", &x, &v);
      was = gett(x, 1);
      update(x, v, 1);
      updatee(x, x, v - was, 1);
      continue;
    }
    if (t == 2) {
      scanf("%I64d %I64d", &l, &r);
      printf("%I64d\n", (1000000000 + go(l, r, 1)) % 1000000000);
      continue;
    }
    if (t == 3) {
      scanf("%I64d %I64d %I64d", &l, &r, &d);
      updatee(l, r, d, 1);
      if (d == 0) continue;
      godown(l, r, d, 1);
      continue;
    }
  }
}
