#include <bits/stdc++.h>
using namespace std;
long long a[200020];
long long f[200020], pref[200020];
const int mod = 1e9;
int p = 0;
struct SegmentTree {
  int l, r, mid;
  long long lazy = 0;
  long long s0, s1;
  SegmentTree *lt, *rt;
  int len() { return r - l + 1; }
  static SegmentTree* niu(int l, int r);
  inline static long long safeget(SegmentTree* node, int i) {
    if (i == 0) return node->s0;
    if (i == 1) return node->s1;
    return (f[i - 2] * node->s0 % mod + f[i - 1] * node->s1 % mod) % mod;
  }
  inline void pullup() {
    pushdown();
    s0 = lt->s0 + safeget(rt, lt->len());
    s0 %= mod;
    s1 = lt->s1 + safeget(rt, lt->len() + 1);
    s1 %= mod;
  }
  inline void modifyone(int p, long long x) {
    if (l == r) {
      a[p] = x;
      s0 = s1 = x;
      return;
    }
    pushdown();
    if (p <= mid) {
      lt->modifyone(p, x);
    } else {
      rt->modifyone(p, x);
    }
    pullup();
  }
  inline void pushdown() {
    if (!lazy) return;
    if (l == r) {
      a[l] += lazy;
      a[l] %= mod;
      lazy = 0;
      return;
    }
    lt->s0 += lazy * pref[lt->len() - 1] % mod;
    lt->s0 %= mod;
    lt->s1 += lazy * (pref[lt->len()] - pref[0]) % mod;
    lt->s1 %= mod;
    lt->lazy += lazy;
    lt->lazy %= mod;
    rt->s0 += lazy * pref[rt->len() - 1] % mod;
    rt->s0 %= mod;
    rt->s1 += lazy * (pref[rt->len()] - pref[0]) % mod;
    rt->s1 %= mod;
    rt->lazy += lazy;
    rt->lazy %= mod;
    lazy = 0;
    pullup();
  }
  inline void modifyrg(int rl, int rr, long long x) {
    if (rl <= l && r <= rr) {
      s0 += x * pref[len() - 1] % mod;
      s0 %= mod;
      s1 += x * (pref[len()] - pref[0]) % mod;
      s1 %= mod;
      lazy += x;
      lazy %= mod;
      return;
    }
    pushdown();
    if (rl <= mid) {
      lt->modifyrg(rl, rr, x);
    }
    if (rr >= mid + 1) {
      rt->modifyrg(rl, rr, x);
    }
    pullup();
  }
  inline long long qry(int rl, int rr) {
    if (rl <= l && r <= rr) {
      return safeget(this, l - rl);
    }
    pushdown();
    long long res = 0;
    if (rl <= mid) {
      res += lt->qry(rl, rr);
      res %= mod;
    }
    if (rr >= mid + 1) {
      res += rt->qry(rl, rr);
      res %= mod;
    }
    return res;
  }
} * root, mall[500000];
SegmentTree* SegmentTree::niu(int l, int r) {
  SegmentTree* thi = &mall[++p];
  thi->l = l;
  thi->r = r;
  thi->mid = (l + r) >> 1;
  thi->lazy = 0;
  if (l == r) {
    thi->s0 = thi->s1 = a[l];
    return thi;
  }
  thi->lt = niu(l, thi->mid);
  thi->rt = niu(thi->mid + 1, r);
  thi->pullup();
  return thi;
}
int n, m;
int main() {
  f[0] = 1;
  f[1] = 1;
  pref[0] = 1;
  pref[1] = 2;
  for (int i = 2; i <= 200000; ++i) {
    f[i] = f[i - 2] + f[i - 1];
    f[i] %= mod;
    pref[i] = pref[i - 1] + f[i];
    pref[i] %= mod;
  }
  scanf("%d %d", &n, &m);
  for (int i = 1; i <= n; ++i) {
    scanf("%lld", &a[i]);
  }
  root = SegmentTree::niu(1, n);
  for (int i = 1, ty, a, b, c; i <= m; ++i) {
    scanf("%d %d %d", &ty, &a, &b);
    if (ty == 1) {
      root->modifyone(a, b);
    } else if (ty == 2) {
      printf("%lld\n", root->qry(a, b));
    } else {
      scanf("%d", &c);
      root->modifyrg(a, b, c);
    }
  }
}
