#include <bits/stdc++.h>
using namespace std;
const double pi = acos(0.0) * 2.0;
const double eps = 1e-12;
const int step[8][2] = {{1, 0}, {-1, 0}, {0, 1},  {0, -1},
                        {1, 1}, {1, -1}, {-1, 1}, {-1, -1}};
template <class T>
inline T abs1(T a) {
  return a < 0 ? -a : a;
}
template <class T>
inline T max1(T a, T b, T c = -1234567, T d = -1234567) {
  T ans = a > b ? a : b;
  if (c != -1234567) ans = max1(ans, c);
  if (d != -1234567) ans = max1(ans, d);
  return ans;
}
template <class T>
inline T min1(T a, T b, T c = -1234567, T d = -1234567) {
  T ans = a < b ? a : b;
  if (c != -1234567) ans = min(ans, c);
  if (d != -1234567) ans = min(ans, d);
  return ans;
}
template <class T>
inline T gcd1(T a, T b) {
  if (a < b) swap(a, b);
  if (a % b == 0) return b;
  return gcd1(b, a % b);
}
template <class T>
inline T lb(T num) {
  return num & (-num);
}
inline int jud(double a, double b) {
  if (abs1(a - b) < eps) return 0;
  if (a < b) return -1;
  return 1;
}
template <typename it, typename t1>
inline int find(t1 val, it a, int na, bool f_small = 1, bool f_lb = 1) {
  if (na == 1) return 0;
  int be = 0, en = na - 1;
  if (*a <= *(a + na - 1)) {
    if (f_lb == 0)
      while (be < en) {
        int mid = (be + en + 1) / 2;
        if (jud(*(a + mid), val) != 1)
          be = mid;
        else
          en = mid - 1;
      }
    else
      while (be < en) {
        int mid = (be + en) / 2;
        if (jud(*(a + mid), val) != -1)
          en = mid;
        else
          be = mid + 1;
      }
    if (f_small && jud(*(a + be), val) == 1 && be != 0) be--;
    if (!f_small && jud(*(a + be), val) == -1 && be != na - 1) be++;
  } else {
    if (f_lb)
      while (be < en) {
        int mid = (be + en + 1) / 2;
        if (jud(*(a + mid), val) != -1)
          be = mid;
        else
          en = mid - 1;
      }
    else
      while (be < en) {
        int mid = (be + en) / 2;
        if (jud(*(a + mid), val) != 1)
          en = mid;
        else
          be = mid + 1;
      }
    if (!f_small && jud(*(a + be), val) == -1 && be != 0) be--;
    if (f_small && jud(*(a + be), val) == 1 && be != na - 1) be++;
  }
  return be;
}
inline int bitnum(unsigned long long nValue) {
  nValue = ((0xaaaaaaaaaaaaaaaaull & nValue) >> 1) +
           (0x5555555555555555ull & nValue);
  nValue = ((0xccccccccccccccccull & nValue) >> 2) +
           (0x3333333333333333ull & nValue);
  nValue = ((0xf0f0f0f0f0f0f0f0ull & nValue) >> 4) +
           (0x0f0f0f0f0f0f0f0full & nValue);
  nValue = ((0xff00ff00ff00ff00ull & nValue) >> 8) +
           (0x00ff00ff00ff00ffull & nValue);
  nValue = ((0xffff0000ffff0000ull & nValue) >> 16) +
           (0x0000ffff0000ffffull & nValue);
  nValue = ((0xffffffff00000000ull & nValue) >> 32) +
           (0x00000000ffffffffull & nValue);
  return nValue;
}
long long pow(long long n, long long m, long long mod = 0) {
  long long ans = 1;
  long long k = n;
  while (m) {
    if (m & 1) {
      ans *= k;
      if (mod) ans %= mod;
    }
    k *= k;
    if (mod) k %= mod;
    m >>= 1;
  }
  return ans;
}
const int maxn = 200100;
const int mod = 1000000000;
int n, nq;
long long fib[maxn], orig[maxn];
long long mat[maxn][2][2];
template <class t>
struct segment_node {
  int be, en;
  t add, sum;
};
template <class t>
struct segment_tree {
  int l;
  segment_node<t> tree[maxn * 4];
  t fibsum[maxn], *fib;
  inline int gleft(int no) { return no << 1; }
  inline int gright(int no) { return (no << 1) + 1; }
  inline int gfa(int no) { return no >> 1; }
  inline segment_tree() { l = 0; }
  inline long long getfibsum(int l, int r) {
    long long rans;
    if (!l)
      rans = fibsum[r];
    else
      rans = fibsum[r] - fibsum[l - 1];
    if (rans < 0) rans += mod;
    return rans;
  }
  inline void init(t *ranfib) {
    fibsum[0] = ranfib[0];
    for (int i = 0; i < n; i++) {
      fibsum[i] = fibsum[i - 1] + ranfib[i];
      if (fibsum[i] > mod) fibsum[i] -= mod;
    }
    fib = ranfib;
  }
  void build(int no, int l, int r, t *a, t *fib) {
    if (l == r) {
      tree[no].be = tree[no].en = l;
      tree[no].add = 0;
      tree[no].sum = (a[l] * fib[l]) % mod;
      tree[no].add = 0;
      return;
    }
    tree[no].be = l;
    tree[no].en = r;
    int mid = (l + r) / 2;
    build(gleft(no), l, mid, a, fib);
    build(gright(no), mid + 1, r, a, fib);
    tree[no].sum = tree[gleft(no)].sum + tree[gright(no)].sum;
    if (tree[no].sum > mod) tree[no].sum -= mod;
    tree[no].add = 0;
  }
  void down(int l, int r, int no, t ranadd, bool f = 0, t temp = 0) {
    if (l <= tree[no].be && r >= tree[no].en) {
      if (f) {
        tree[no].sum = ((ranadd - temp + mod) % mod * fib[l]) % mod;
        if (tree[no].sum > mod) tree[no].sum -= mod;
      } else {
        tree[no].add += ranadd;
        tree[no].sum += (ranadd * getfibsum(tree[no].be, tree[no].en)) % mod;
        if (tree[no].sum > mod) tree[no].sum -= mod;
      }
      return;
    }
    int mid = (tree[no].be + tree[no].en) / 2;
    if (r >= tree[no].be && l <= mid)
      down(l, r, gleft(no), ranadd, f, temp + tree[no].add);
    if (r >= mid + 1 && l <= tree[no].en)
      down(l, r, gright(no), ranadd, f, temp + tree[no].add);
    tree[no].sum = (tree[no].add * getfibsum(tree[no].be, tree[no].en)) % mod +
                   (tree[gleft(no)].sum + tree[gright(no)].sum) % mod;
    if (tree[no].sum > mod) tree[no].sum -= mod;
  }
  t getsum(int l, int r, int no) {
    if (l > r) return 0;
    if (l <= tree[no].be && r >= tree[no].en) return tree[no].sum;
    t ans = 0;
    int mid = (tree[no].be + tree[no].en) / 2;
    if (r >= tree[no].be && l <= mid)
      ans += getsum(max1(l, tree[no].be), min1(r, mid), gleft(no));
    if (ans > mod) ans -= mod;
    if (r >= mid + 1 && l <= tree[no].en)
      ans += getsum(max1(l, mid + 1), min1(r, tree[no].en), gright(no));
    if (ans > mod) ans -= mod;
    ans += (tree[no].add * getfibsum(l, r)) % mod;
    if (ans > mod) ans -= mod;
    return ans;
  }
};
segment_tree<long long> sgt1, sgt2;
int main() {
  scanf("%d%d", &n, &nq);
  for (int i = 0; i < n; i++) scanf("%I64d", orig + i);
  fib[0] = 0;
  fib[1] = 1;
  for (int i = 2; i < n + 2; i++) {
    fib[i] = fib[i - 1] + fib[i - 2];
    if (fib[i] > mod) fib[i] -= mod;
  }
  sgt1.init(fib + 1);
  sgt2.init(fib);
  sgt1.build(1, 0, n - 1, orig, fib + 1);
  sgt2.build(1, 0, n - 1, orig, fib);
  mat[0][0][0] = 1;
  mat[0][0][1] = 0;
  mat[0][1][0] = 0;
  mat[0][1][1] = 1;
  mat[1][0][0] = 0;
  mat[1][0][1] = 1;
  mat[1][1][0] = 1;
  mat[1][1][1] = -1;
  for (int i = 2; i <= n; i++) {
    mat[i][0][0] =
        (mat[i - 1][0][0] * mat[1][0][0] + mat[i - 1][0][1] * mat[1][1][0]) %
        mod;
    mat[i][1][0] =
        (mat[i - 1][1][0] * mat[1][0][0] + mat[i - 1][1][1] * mat[1][1][0]) %
        mod;
    mat[i][0][1] =
        (mat[i - 1][0][0] * mat[1][0][1] + mat[i - 1][0][1] * mat[1][1][1]) %
        mod;
    mat[i][1][1] =
        (mat[i - 1][1][0] * mat[1][0][1] + mat[i - 1][1][1] * mat[1][1][1]) %
        mod;
  }
  for (int i = 0; i < nq; i++) {
    int cate;
    scanf("%d", &cate);
    switch (cate) {
      case 1: {
        int x, v;
        scanf("%d%d", &x, &v);
        sgt1.down(x - 1, x - 1, 1, v, 1);
        sgt2.down(x - 1, x - 1, 1, v, 1);
        break;
      }
      case 2: {
        int l, r;
        scanf("%d%d", &l, &r);
        long long a = sgt1.getsum(l - 1, r - 1, 1);
        long long b = sgt2.getsum(l - 1, r - 1, 1);
        a = (mat[l - 1][0][0] * a + mat[l - 1][0][1] * b) % mod;
        if (a < 0) a += mod;
        cout << a << endl;
        break;
      }
      case 3: {
        int l, r, v;
        scanf("%d%d%d", &l, &r, &v);
        sgt1.down(l - 1, r - 1, 1, v);
        sgt2.down(l - 1, r - 1, 1, v);
        break;
      }
    }
  }
  return 0;
}
