#include <bits/stdc++.h>
using namespace std;
int n, m;
int f[200005], s[200005];
struct T {
  int v1, v2, tag;
} t[200005 << 2];
const int p = 1e9;
inline int read() {
  int x = 0, f = 1;
  char ch = getchar();
  while (ch > '9' || ch < '0') {
    if (ch == '-') f = -1;
    ch = getchar();
    if (ch == -1) return 0;
  }
  while (ch >= '0' && ch <= '9') {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  return x * f;
}
inline void pushup(int rt, int l, int r) {
  int mid = (l + r) >> 1;
  if (l == mid)
    t[rt].v1 = (t[(rt << 1)].v1 + t[(rt << 1 | 1)].v2) % p;
  else
    t[rt].v1 =
        (t[(rt << 1)].v1 + (1ll * t[(rt << 1 | 1)].v1 * f[mid - l - 1] % p +
                            1ll * t[(rt << 1 | 1)].v2 * f[mid - l] % p) %
                               p) %
        p;
  t[rt].v2 =
      (t[(rt << 1)].v2 + (1ll * t[(rt << 1 | 1)].v1 * f[mid - l] % p +
                          1ll * t[(rt << 1 | 1)].v2 * f[mid - l + 1] % p) %
                             p) %
      p;
}
inline void pushdown(int rt, int l, int r) {
  if (t[rt].tag) {
    int mid = (l + r) >> 1;
    t[(rt << 1)].tag = (t[(rt << 1)].tag + t[rt].tag) % p,
             t[(rt << 1)].v1 =
                 (t[(rt << 1)].v1 + 1ll * s[mid - l] * t[rt].tag % p) % p,
             t[(rt << 1)].v2 = (t[(rt << 1)].v2 +
                                1ll * (s[mid - l + 1] - 1) * t[rt].tag % p) %
                               p;
    t[(rt << 1 | 1)]
        .tag = (t[(rt << 1 | 1)].tag + t[rt].tag) % p,
     t[(rt << 1 | 1)].v1 =
         (t[(rt << 1 | 1)].v1 + 1ll * s[r - mid - 1] * t[rt].tag % p) % p,
     t[(rt << 1 | 1)].v2 =
         (t[(rt << 1 | 1)].v2 + 1ll * (s[r - mid] - 1) * t[rt].tag % p) % p;
    t[rt].tag = 0;
  }
}
void update(int rt, int l, int r, int L, int R, int v) {
  if (L <= l && r <= R) {
    t[rt].tag = (t[rt].tag + v) % p,
    t[rt].v1 = (t[rt].v1 + 1ll * s[r - l] * v % p) % p,
    t[rt].v2 = (t[rt].v2 + 1ll * (s[r - l + 1] - 1) * v % p) % p;
    return;
  }
  pushdown(rt, l, r);
  int mid = (l + r) >> 1;
  if (L <= mid) update((rt << 1), l, mid, L, R, v);
  if (mid < R) update((rt << 1 | 1), mid + 1, r, L, R, v);
  pushup(rt, l, r);
}
int query(int rt, int l, int r, int L, int R) {
  if (L <= l && r <= R)
    if (l == L)
      return t[rt].v1;
    else if (l == L + 1)
      return t[rt].v2;
    else
      return (1ll * t[rt].v1 * f[l - L - 2] % p +
              1ll * t[rt].v2 * f[l - L - 1] % p) %
             p;
  pushdown(rt, l, r);
  int mid = (l + r) >> 1, ans = 0;
  if (L <= mid) ans += query((rt << 1), l, mid, L, R);
  if (mid < R) ans += query((rt << 1 | 1), mid + 1, r, L, R);
  return ans % p;
}
int main() {
  n = read(), m = read(), f[0] = f[1] = s[0] = 1, s[1] = 2;
  for (int i = 2; i <= n; i++)
    f[i] = (f[i - 1] + f[i - 2]) % p, s[i] = (s[i - 1] + f[i]) % p;
  for (int i = 1, x; i <= n; i++) x = read(), update(1, 1, n, i, i, x);
  while (m--) {
    int opt, l, r, x;
    opt = read(), l = read(), r = read();
    if (opt == 1)
      update(1, 1, n, l, l, r - query(1, 1, n, l, l));
    else if (opt == 2)
      printf("%d\n", query(1, 1, n, l, r));
    else
      x = read(), update(1, 1, n, l, r, x);
  }
  return 0;
}
