#include <bits/stdc++.h>
typedef struct {
  long long int x, y;
} ele;
long long int mod = 1000000000;
int n, m, nn;
long long int f[500514];
long long int sumf[500514];
ele bst1[3000514];
long long int bst3[3000514];
int bst4[3000514];
ele mov(ele a, long long int k) {
  if (k == 0) return a;
  if (k == 1) return (ele){(a.x + a.y) % mod, a.x};
  long long int naf1 = (a.x * f[k] % mod + a.y * f[k - 1] % mod) % mod;
  long long int naf2 = (a.x * f[k - 1] % mod + a.y * f[k - 2] % mod) % mod;
  return (ele){naf1, naf2};
}
ele add(ele a, long long int k, long long int l) {
  a.x = (a.x + k * sumf[l - 1] % mod) % mod;
  if (l - 2 >= 0) {
    a.y = (a.y + k * sumf[l - 2] % mod) % mod;
  }
  return a;
}
void mdy(int q, int ts, int te, int w, long long int x) {
  if (ts == q && ts + 1 == te) {
    bst1[w] = (ele){x, 0};
    return;
  }
  int m = (ts + te) / 2;
  if (q < m)
    mdy(q, ts, m, w + w, x);
  else
    mdy(q, m, te, w + w + 1, x);
  bst1[w] = mov(bst1[w + w + 1], m - ts);
  bst1[w].x = (bst1[w].x + bst1[w + w].x) % mod;
  bst1[w].y = (bst1[w].y + bst1[w + w].y) % mod;
}
ele qry(int qs, int qe, int ts, int te, int w) {
  if (qs <= ts && te <= qe) {
    return bst1[w];
  }
  int m = (ts + te) / 2;
  ele l = m > qs ? qry(qs, qe, ts, m, w + w) : (ele){0, 0};
  ele r = qe > m ? qry(qs, qe, m, te, w + w + 1) : (ele){0, 0};
  ele ans = mov(r, m > qs ? std::min(m, qe) - std::max(qs, ts) : 0);
  ans.x = (ans.x + l.x) % mod;
  ans.y = (ans.y + l.y) % mod;
  return ans;
}
void sub(int qs, int qe, int ts, int te, int w, long long int d) {
  if (qs <= ts && te <= qe) {
    bst3[w] = (bst3[w] + d + mod) % mod;
    return;
  }
  int m = (ts + te) / 2;
  if (m > qs) sub(qs, qe, ts, m, w + w, d);
  if (qe > m) sub(qs, qe, m, te, w + w + 1, d);
  ele l = qry(ts, m, ts, m, w + w);
  ele r = qry(m, te, m, te, w + w + 1);
  bst1[w] = mov(r, m - ts);
  bst1[w].x = (bst1[w].x + l.x) % mod;
  bst1[w].y = (bst1[w].y + l.y) % mod;
}
int main() {
  scanf("%d %d", &n, &m);
  for (nn = n; nn != (nn & -nn); nn += (nn & -nn))
    ;
  f[0] = f[1] = 1;
  sumf[0] = 1;
  sumf[1] = 2;
  for (int i = 2; i <= 500000; i++) {
    f[i] = (f[i - 1] + f[i - 2]) % mod;
    sumf[i] = (sumf[i - 1] + f[i]) % mod;
  }
  for (int i = 0; i < n; i++) {
    long long int a;
    scanf("%I64d", &a);
    mdy(i, 0, nn, 1, a);
  }
  for (int i = 0; i < m; i++) {
    int t;
    scanf("%d", &t);
    if (t == 1) {
      int x;
      long long int v;
      scanf("%d %I64d", &x, &v);
      mdy(x - 1, 0, nn, 1, v);
    }
    if (t == 2) {
      int l, r;
      scanf("%d %d", &l, &r);
      ele ans = qry(l - 1, r, 0, nn, 1);
      printf("%I64d\n", ans.x);
    }
    if (t == 3) {
      int l, r;
      long long int d;
      scanf("%d %d %I64d", &l, &r, &d);
      sub(l - 1, r, 0, nn, 1, d);
    }
  }
  return 0;
}
