#include <bits/stdc++.h>
using namespace std;
inline int readint() {
  int num = 0;
  char c = getchar();
  if (c == '-') return -readint();
  while (c >= '0' && c <= '9') {
    num = (num << 3) + (num << 1) + c - '0';
    c = getchar();
  }
  return num;
}
struct matrix {
  long long m[2][2];
  inline matrix() {}
  inline matrix(int a) { m[0][0] = m[0][1] = m[1][0] = m[1][1] = a; }
  inline matrix(int a, int b, int c, int d) {
    m[0][0] = a;
    m[0][1] = b;
    m[1][0] = c;
    m[1][1] = d;
  }
};
inline matrix Plus(matrix a, matrix b) {
  return matrix((a.m[0][0] + b.m[0][0]) % 1000000000,
                (a.m[0][1] + b.m[0][1]) % 1000000000,
                (a.m[1][0] + b.m[1][0]) % 1000000000,
                (a.m[1][1] + b.m[1][1]) % 1000000000);
}
inline void Plusto(matrix& a, matrix b) {
  a.m[0][0] = (a.m[0][0] + b.m[0][0]) % 1000000000;
  a.m[0][1] = (a.m[0][1] + b.m[0][1]) % 1000000000;
  a.m[1][0] = (a.m[1][0] + b.m[1][0]) % 1000000000;
  a.m[1][1] = (a.m[1][1] + b.m[1][1]) % 1000000000;
}
inline matrix times(matrix a, matrix b) {
  return matrix((a.m[0][0] * b.m[0][0] % 1000000000 +
                 a.m[0][1] * b.m[1][0] % 1000000000) %
                    1000000000,
                (a.m[0][0] * b.m[0][1] % 1000000000 +
                 a.m[0][1] * b.m[1][1] % 1000000000) %
                    1000000000,
                (a.m[1][0] * b.m[0][0] % 1000000000 +
                 a.m[1][1] * b.m[1][0] % 1000000000) %
                    1000000000,
                (a.m[1][0] * b.m[0][1] % 1000000000 +
                 a.m[1][1] * b.m[1][1] % 1000000000) %
                    1000000000);
}
inline void timesto(matrix& a, matrix b) {
  a = matrix((a.m[0][0] * b.m[0][0] % 1000000000 +
              a.m[0][1] * b.m[1][0] % 1000000000) %
                 1000000000,
             (a.m[0][0] * b.m[0][1] % 1000000000 +
              a.m[0][1] * b.m[1][1] % 1000000000) %
                 1000000000,
             (a.m[1][0] * b.m[0][0] % 1000000000 +
              a.m[1][1] * b.m[1][0] % 1000000000) %
                 1000000000,
             (a.m[1][0] * b.m[0][1] % 1000000000 +
              a.m[1][1] * b.m[1][1] % 1000000000) %
                 1000000000);
}
matrix fibs[200007] = {matrix(1, 0, 0, 1), matrix(1, 1, 1, 0)},
       fibq[200007] = {matrix(0), matrix(1, 0, 0, 1)};
matrix dt[2000007], ic[2000007];
int n, k;
inline void LiSimon() {
  for (int i = 2; i < 200007; i++) fibs[i] = times(fibs[i - 1], fibs[1]);
  for (int i = 2; i < 200007; i++) fibq[i] = Plus(fibq[i - 1], fibs[i - 1]);
}
inline void YangAnnie(int now, int nl, int nr, int djg, int what) {
  int m = (nl + nr) / 2;
  if (ic[now].m[0][0]) {
    Plusto(dt[now * 2], times(fibq[m - nl + 1], ic[now]));
    Plusto(dt[now * 2 + 1], times(fibq[nr - m], ic[now]));
    Plusto(ic[now * 2], ic[now]);
    Plusto(ic[now * 2 + 1], ic[now]);
    ic[now] = matrix(0);
  }
  if (nl == djg && nr == djg) {
    dt[now].m[0][0] = what;
    dt[now].m[1][0] = what;
    return;
  }
  if (m >= djg)
    YangAnnie(now * 2, nl, m, djg, what);
  else
    YangAnnie(now * 2 + 1, m + 1, nr, djg, what);
  dt[now] = Plus(times(fibs[m - nl + 1], dt[now * 2 + 1]), dt[now * 2]);
}
inline matrix YanZack(int now, int nl, int nr, int l, int r) {
  if (nl > r || nr < l) return matrix(0);
  int m = (nl + nr) / 2;
  if (ic[now].m[0][0]) {
    Plusto(dt[now * 2], times(fibq[m - nl + 1], ic[now]));
    Plusto(dt[now * 2 + 1], times(fibq[nr - m], ic[now]));
    Plusto(ic[now * 2], ic[now]);
    Plusto(ic[now * 2 + 1], ic[now]);
    ic[now] = matrix(0);
  }
  if (nl >= l && nr <= r) {
    return times(fibs[nl - l], dt[now]);
  }
  return Plus(YanZack(now * 2, nl, m, l, r),
              YanZack(now * 2 + 1, m + 1, nr, l, r));
}
inline void SunSandy(int now, int nl, int nr, int l, int r, int what) {
  if (nl > r || nr < l) return;
  int m = (nl + nr) / 2;
  if (ic[now].m[0][0]) {
    Plusto(dt[now * 2], times(fibq[m - nl + 1], ic[now]));
    Plusto(dt[now * 2 + 1], times(fibq[nr - m], ic[now]));
    Plusto(ic[now * 2], ic[now]);
    Plusto(ic[now * 2 + 1], ic[now]);
    ic[now] = matrix(0);
  }
  if (nl >= l && nr <= r) {
    ic[now].m[0][0] += what;
    ic[now].m[1][0] += what;
    Plusto(dt[now], times(fibq[nr - nl + 1], ic[now]));
    return;
  }
  SunSandy(now * 2, nl, m, l, r, what);
  SunSandy(now * 2 + 1, m + 1, nr, l, r, what);
  dt[now] = Plus(times(fibs[m - nl + 1], dt[now * 2 + 1]), dt[now * 2]);
}
inline void LiAmy() {
  int a = readint(), b = readint();
  a--, b--;
  printf("%I64d\n", YanZack(1, 0, n - 1, a, b).m[1][0]);
}
inline void SunTom() {
  int a = readint(), b = readint(), c = readint();
  a--, b--;
  SunSandy(1, 0, n - 1, a, b, c);
}
inline void ZhuMary() {
  int a = readint(), b = readint();
  a--;
  YangAnnie(1, 0, n - 1, a, b);
}
inline void XuanAlex() {
  n = readint();
  k = readint();
  for (int i = 0; i < n; i++) {
    int a = readint();
    YangAnnie(1, 0, n - 1, i, a);
  }
  for (int i = 0; i < k; i++) {
    int mode = readint();
    if (mode == 1)
      ZhuMary();
    else if (mode == 2)
      LiAmy();
    else
      SunTom();
  }
}
int main() {
  LiSimon();
  XuanAlex();
  return 0;
}
