#include <bits/stdc++.h>
using namespace std;
const int MOD = 1000000000, dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};
const double eps = 1e-8;
void read(int &k) {
  k = 0;
  char x = getchar();
  while (x < '0' || x > '9') x = getchar();
  while (x >= '0' && x <= '9') {
    k = k * 10 - 48 + x;
    x = getchar();
  }
}
int n, m, x, y, z, type, a[200010];
struct matrix {
  int a[2][2];
  matrix(int a0, int a1, int a2, int a3) {
    a[0][0] = a0;
    a[0][1] = a1;
    a[1][0] = a2;
    a[1][1] = a3;
  }
  matrix() { memset(a, 0, sizeof a); }
  matrix operator*(const matrix &b) const {
    matrix ret;
    for (int i = 0; i < 2; i++)
      for (int j = 0; j < 2; j++) {
        for (int k = 0; k < 2; k++)
          ret.a[i][j] += 1ll * a[i][k] * b.a[k][j] % MOD;
        ret.a[i][j] %= MOD;
      }
    return ret;
  }
  matrix operator+(const matrix &b) const {
    matrix ret;
    for (int i = 0; i < 2; i++)
      for (int j = 0; j < 2; j++) ret.a[i][j] = (a[i][j] + b.a[i][j]) % MOD;
    return ret;
  }
} M[200010];
struct node {
  matrix sum;
  int mark, siz;
};
inline void update(node &x, const node &y, const node &z) {
  x.siz = y.siz + z.siz;
  x.sum = y.sum + M[y.siz] * z.sum;
}
struct SegmentTree {
  node c[524288];
  void maketree(int L, int R, int now) {
    if (L == R) {
      c[now] = (node){matrix(1, 0, 0, 1) * matrix(a[L], 0, 0, 0), 0, 1};
      return;
    }
    int t = (L + R) >> 1;
    maketree(L, t, now * 2);
    maketree(t + 1, R, now * 2 + 1);
    update(c[now], c[now * 2], c[now * 2 + 1]);
  }
  node ask(int L, int R, int l, int r, int now) {
    if (L == l && R == r) return c[now];
    int t = (L + R) >> 1;
    if (r <= t) return ask(L, t, l, r, now * 2);
    if (l > t) return ask(t + 1, R, l, r, now * 2 + 1);
    node ret;
    update(ret, ask(L, t, l, t, now * 2), ask(t + 1, R, t + 1, r, now * 2 + 1));
    return ret;
  }
  void chg(int L, int R, int x, int y, int now) {
    if (L == R) {
      c[now] = (node){matrix(1, 0, 0, 1) * matrix(y, 0, 0, 0), 0, 1};
      return;
    }
    int t = (L + R) >> 1;
    if (x <= t)
      chg(L, t, x, y, now * 2);
    else if (x > t)
      chg(t + 1, R, x, y, now * 2 + 1);
    update(c[now], c[now * 2], c[now * 2 + 1]);
  }
  void modify(int L, int R, int l, int r, int z, int now) {
    if (L == l && R == r) {
    }
  }
  int asknum(int L, int R, int pos, int now) {
    if (L == R) return (c[now].sum.a[0][0] + c[now].sum.a[1][0]) % MOD;
    int t = (L + R) >> 1;
    if (pos <= t)
      return asknum(L, t, pos, now * 2);
    else
      return asknum(t + 1, R, pos, now * 2 + 1);
  }
} xds;
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) scanf("%d", a + i);
  M[0] = matrix(1, 0, 0, 1);
  for (int i = 1; i <= n; i++) M[i] = M[i - 1] * matrix(1, 1, 1, 0);
  xds.maketree(1, n, 1);
  for (; m--;) {
    scanf("%d%d%d", &type, &x, &y);
    if (type == 1)
      xds.chg(1, n, x, y, 1);
    else if (type == 2) {
      int ans = 0;
      if (x < y) {
        matrix ret = xds.ask(1, n, x + 1, y, 1).sum;
        ans = (ret.a[0][0] + ret.a[1][0]) % MOD;
      }
      ans = (ans + xds.asknum(1, n, x, 1)) % MOD;
      cout << ans << endl;
    } else if (type == 3) {
      scanf("%d", &z);
      xds.modify(1, n, x, y, z, 1);
    }
  }
  return 0;
}
