#include <bits/stdc++.h>
using namespace std;
const int L = 18;
const int MAXN = 1 << L;
const int MOD = 1000000000;
int _f[MAXN];
int* f = _f + 2;
struct T {
  int len;
  int sum1, sum2;
  T() {
    len = 0;
    sum1 = 0;
    sum2 = 0;
  }
  T(int v) {
    len = 1;
    sum1 = v;
    sum2 = 0;
  }
  T(int len, int sum1, int sum2) : len(len), sum1(sum1), sum2(sum2) {}
};
T operator+(const T& l, const T& r) {
  return T(l.len + r.len,
           (l.sum1 + (long long)f[l.len - 2] * r.sum1 +
            (long long)f[l.len - 1] * r.sum2) %
               MOD,
           (l.sum2 + (long long)f[l.len - 1] * r.sum1 +
            (long long)f[l.len - 0] * r.sum2) %
               MOD);
}
T operator+(const T& t, int d) {
  return T(t.len, (t.sum1 + (long long)d * f[t.len - 1]) % MOD,
           (t.sum2 + (long long)d * (f[t.len] - 1)) % MOD);
}
T a[MAXN * 2];
int d[MAXN * 2];
void com(int i) { a[i] = a[i * 2] + a[i * 2 + 1] + d[i]; }
void add(int i, int d) {
  a[i] = a[i] + d;
  ::d[i] = (::d[i] + d) % MOD;
}
void push(int i) {
  add(i * 2, d[i]);
  add(i * 2 + 1, d[i]);
  d[i] = 0;
}
void flush(int pos) {
  for (int i = L; i > 0; i--) push(pos >> i);
}
void renew(int pos) {
  pos /= 2;
  while (pos) {
    com(pos);
    pos /= 2;
  }
}
int main() {
  int n, m;
  int i, j, k;
  scanf("%d%d", &n, &m);
  f[-1] = 0;
  f[-2] = 1;
  f[0] = f[1] = 1;
  for (i = 2; i <= n; i++) f[i] = (f[i - 1] + f[i - 2]) % MOD;
  for (i = 1; i <= n; i++) {
    scanf("%d", &j);
    a[i + MAXN] = T(j);
  }
  for (i = MAXN - 1; i > 0; i--) com(i);
  while (m--) {
    scanf("%d", &i);
    if (i == 1) {
      scanf("%d%d", &i, &j);
      flush(i + MAXN);
      a[i + MAXN] = T(j);
      d[i + MAXN] = 0;
      renew(i + MAXN);
    } else if (i == 2) {
      int l, r;
      T lans, rans;
      scanf("%d%d", &l, &r);
      l--;
      r++;
      l += MAXN;
      r += MAXN;
      flush(l);
      flush(r);
      while (r - l > 1) {
        if (~l & 1) lans = lans + a[l ^ 1];
        if (r & 1) rans = a[r ^ 1] + rans;
        l /= 2;
        r /= 2;
      }
      lans = lans + rans;
      printf("%d\n", (lans.sum1 + lans.sum2) % MOD);
    } else if (i == 3) {
      int l, r, d;
      int tl, tr;
      scanf("%d%d%d", &l, &r, &d);
      l--;
      r++;
      l += MAXN;
      r += MAXN;
      tl = l;
      tr = r;
      while (r - l > 1) {
        if (~l & 1) add(l ^ 1, d);
        if (r & 1) add(r ^ 1, d);
        l /= 2;
        r /= 2;
      }
      renew(tl);
      renew(tr);
    }
  }
  return 0;
}
