#include <bits/stdc++.h>
using namespace std;
inline void read(int &x) {
  x = 0;
  int f = 1;
  char ch = getchar();
  while ((ch < '0' || ch > '9') && ch != '-') ch = getchar();
  if (ch == '-') {
    f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  x *= f;
}
const int N = 2e5 + 10, mod = 1e9;
struct matri {
  int m, n, num[2][2];
  friend matri operator*(matri aa, matri bb) {
    matri ret;
    ret.n = bb.n, ret.m = aa.m;
    ret.num[0][0] = ((long long)aa.num[0][0] * bb.num[0][0] +
                     (long long)aa.num[1][0] * bb.num[0][1]) %
                    mod;
    ret.num[1][0] = ((long long)aa.num[0][0] * bb.num[1][0] +
                     (long long)aa.num[1][0] * bb.num[1][1]) %
                    mod;
    if (ret.m == 2) {
      ret.num[0][1] = ((long long)aa.num[0][1] * bb.num[0][0] +
                       (long long)aa.num[1][1] * bb.num[0][1]) %
                      mod;
      ret.num[1][1] = ((long long)aa.num[0][1] * bb.num[1][0] +
                       (long long)aa.num[1][1] * bb.num[1][1]) %
                      mod;
    }
    return ret;
  }
  friend matri operator+(matri aa, matri bb) {
    aa.num[0][0] = (aa.num[0][0] + bb.num[0][0]) % mod;
    aa.num[1][0] = (aa.num[1][0] + bb.num[1][0]) % mod;
    if (aa.m == 2) {
      aa.num[0][1] = (aa.num[0][1] + bb.num[0][1]) % mod;
      aa.num[1][1] = (aa.num[1][1] + bb.num[1][1]) % mod;
    }
    return aa;
  }
} c[N], sum[N];
struct Tree {
  matri ans;
  int lazy, len;
  friend Tree operator+(Tree aa, Tree bb) {
    bb.ans = bb.ans * c[aa.len] + aa.ans;
    bb.len = aa.len + bb.len;
    return bb;
  }
} a[N << 2];
int val[N];
void push_up(int rt) {
  int tmp = a[rt].lazy;
  a[rt] = a[rt << 1] + a[rt << 1 | 1];
  a[rt].lazy = tmp;
}
void push_down(int l, int r, int rt) {
  int mid = (l + r) / 2;
  if (a[rt].lazy == 0) return;
  a[rt << 1].lazy = (a[rt << 1].lazy + a[rt].lazy) % mod;
  a[rt << 1 | 1].lazy = (a[rt << 1 | 1].lazy + a[rt].lazy) % mod;
  matri tmp;
  tmp.n = 2, tmp.m = 1, tmp.num[0][0] = a[rt].lazy, tmp.num[1][0] = 0;
  a[rt << 1].ans = a[rt << 1].ans + tmp * sum[mid - l + 1];
  a[rt << 1 | 1].ans = a[rt << 1 | 1].ans + tmp * sum[r - mid];
  a[rt].lazy = 0;
}
void build(int l, int r, int rt) {
  if (l == r) {
    a[rt].len = 1;
    a[rt].ans.n = 2;
    a[rt].ans.m = 1;
    a[rt].ans.num[0][0] = val[l];
    return;
  }
  int mid = (l + r) / 2;
  build(l, mid, rt << 1);
  build(mid + 1, r, rt << 1 | 1);
  push_up(rt);
}
void updata(int l, int r, int rt, int x, int y, int c, int op) {
  if (x <= l && y >= r) {
    if (op == 1)
      a[rt].ans.num[0][0] = c;
    else {
      a[rt].lazy = (a[rt].lazy + c) % mod;
      matri tmp;
      tmp.n = 2, tmp.m = 1, tmp.num[0][0] = c, tmp.num[1][0] = 0;
      a[rt].ans = a[rt].ans + tmp * sum[r - l + 1];
    }
    return;
  }
  push_down(l, r, rt);
  int mid = (l + r) / 2;
  if (x <= mid) updata(l, mid, rt << 1, x, y, c, op);
  if (y > mid) updata(mid + 1, r, rt << 1 | 1, x, y, c, op);
  push_up(rt);
}
Tree quert(int l, int r, int rt, int x, int y) {
  if (x <= l && y >= r) return a[rt];
  int mid = (l + r) / 2;
  push_down(l, r, rt);
  int pd = 0;
  Tree ret;
  if (x <= mid) {
    ret = quert(l, mid, rt << 1, x, y);
    pd = 1;
  }
  if (y > mid) {
    if (pd == 0)
      ret = quert(mid + 1, r, rt << 1 | 1, x, y);
    else
      ret = ret + quert(mid + 1, r, rt << 1 | 1, x, y);
  }
  return ret;
}
int i, j, k, m, n, s, t;
signed main() {
  read(n), read(m);
  c[1].n = c[1].m = 2;
  c[1].num[0][0] = c[1].num[0][1] = c[1].num[1][0] = 1;
  for (i = 2; i <= n; i++) c[i] = c[i - 1] * c[1];
  sum[1].n = sum[1].m = 2;
  sum[1].num[0][0] = sum[0].num[1][1] = 1;
  sum[1].num[0][1] = sum[0].num[1][0] = 0;
  for (i = 2; i <= n; i++) sum[i] = sum[i - 1] + c[i - 1];
  for (i = 1; i <= n; i++) read(val[i]);
  build(1, n, 1);
  for (i = 1; i <= m; i++) {
    int x, y, z, op;
    read(op), read(x), read(y);
    if (op == 1) updata(1, n, 1, x, x, y, op);
    if (op == 2) printf("%d\n", quert(1, n, 1, x, y).ans.num[0][0]);
    if (op == 3) {
      read(z);
      updata(1, n, 1, x, y, z, 3);
    }
  }
  return 0;
}
