#include <bits/stdc++.h>
using namespace std;
const int mo = 1e9;
const double pi = acos(-1);
int f[210000], Sum[210000];
int n, m;
struct seg_tree {
  int s1[210000 * 4], s2[210000 * 4], sign[210000 * 4];
  void modify(int p, int s, int l, int r) {
    s1[p] = (s1[p] + 1ll * s * Sum[r - l]) % mo;
    s2[p] = (s2[p] + 1ll * s * (Sum[r - l + 1] - 1)) % mo;
    sign[p] = (sign[p] + s) % mo;
  }
  void updata(int p, int l, int r) {
    if (sign[p]) {
      int mid = (l + r) / 2;
      modify(p * 2, sign[p], l, mid);
      modify(p * 2 + 1, sign[p], mid + 1, r);
      sign[p] = 0;
    }
  }
  int move(int s1, int s2, int k) {
    if (k == -1) return s1;
    return (1ll * s1 * (k == 0 ? 0 : f[k - 1]) + 1ll * s2 * f[k]) % mo;
  }
  void renew(int p, int l, int r) {
    int mid = (l + r) / 2, k = mid - l;
    s1[p] = (move(s1[p * 2 + 1], s2[p * 2 + 1], k) + s1[p * 2]) % mo;
    s2[p] = (move(s1[p * 2 + 1], s2[p * 2 + 1], k + 1) + s2[p * 2]) % mo;
  }
  void change(int p, int l, int r, int x, int k) {
    if (l == r) {
      s1[p] = s2[p] = k;
      return;
    }
    updata(p, l, r);
    int mid = (l + r) / 2;
    if (x <= mid)
      change(p * 2, l, mid, x, k);
    else
      change(p * 2 + 1, mid + 1, r, x, k);
    renew(p, l, r);
  }
  void add(int p, int l, int r, int x, int y, int k) {
    if (x <= l && y >= r) {
      modify(p, k, l, r);
      return;
    }
    int mid = (l + r) / 2;
    updata(p, l, r);
    if (x <= mid) add(p * 2, l, mid, x, y, k);
    if (y > mid) add(p * 2 + 1, mid + 1, r, x, y, k);
    renew(p, l, r);
  }
  int query(int p, int l, int r, int x, int y) {
    if (x <= l && y >= r) {
      return move(s1[p], s2[p], l - x - 1);
    }
    updata(p, l, r);
    int mid = (l + r) / 2, ans = 0;
    if (x <= mid) ans = query(p * 2, l, mid, x, y);
    if (y > mid) ans = (ans + query(p * 2 + 1, mid + 1, r, x, y)) % mo;
    return ans;
  }
} T;
int main() {
  f[0] = 1;
  Sum[0] = 1;
  f[1] = 1;
  Sum[1] = 2;
  scanf("%d%d", &n, &m);
  for (int i = 2; i <= n; ++i) {
    f[i] = (f[i - 1] + f[i - 2]) % mo;
    Sum[i] = (Sum[i - 1] + f[i]) % mo;
  }
  for (int i = 1; i <= n; ++i) {
    int x;
    scanf("%d", &x);
    T.change(1, 1, n, i, x);
  }
  for (int i = 1; i <= m; ++i) {
    int type, x, y, k;
    scanf("%d", &type);
    if (type == 1) {
      scanf("%d%d", &x, &k);
      T.change(1, 1, n, x, k);
    } else if (type == 2) {
      scanf("%d%d", &x, &y);
      printf("%d\n", (T.query(1, 1, n, x, y) + mo) % mo);
    } else {
      scanf("%d%d%d", &x, &y, &k);
      T.add(1, 1, n, x, y, k);
    }
  }
}
