#include <bits/stdc++.h>
using namespace std;
const int mod = 1000000000;
const int maxn = 200020;
struct Martix {
  static const int maxs = 2;
  long long c[maxs][maxs];
  Martix() { memset(c, 0, sizeof(c)); }
  void init() {
    c[0][0] = c[1][1] = 1;
    c[0][1] = c[1][0] = 0;
  }
  Martix operator*(const Martix& rhs) const {
    Martix ret;
    for (int i = 0; i < maxs; ++i) {
      for (int j = 0; j < maxs; ++j) {
        ret.c[i][j] = 0;
        for (int k = 0; k < maxs; ++k) {
          ret.c[i][j] += c[i][k] * rhs.c[k][j] % mod;
          ret.c[i][j] %= mod;
        }
      }
    }
    return ret;
  }
} mat[maxn], base;
void init(int n) {
  base.c[0][0] = base.c[0][1] = base.c[1][0] = 1;
  base.c[1][1] = 0;
  mat[0].init();
  for (int i = 1; i <= n; ++i) {
    mat[i] = mat[i - 1] * base;
  }
}
struct SegTree {
  static const int maxs = maxn * 4;
  int left[maxs], right[maxs];
  long long sf[maxs][2];
  void pushUp(int t) {
    int len = right[t << 1] - left[t << 1] + 1;
    sf[t][0] = sf[t << 1][0];
    sf[t][1] = sf[t << 1][1];
    sf[t][1] += sf[t << 1 | 1][0] * mat[len].c[0][1] % mod;
    sf[t][1] %= mod;
    sf[t][1] += sf[t << 1 | 1][1] * mat[len].c[1][1] % mod;
    sf[t][1] %= mod;
    sf[t][0] += sf[t << 1 | 1][0] * mat[len].c[0][0] % mod;
    sf[t][0] %= mod;
    sf[t][0] += sf[t << 1 | 1][1] * mat[len].c[1][0] % mod;
    sf[t][0] %= mod;
  }
  void build(int t, int l, int r, int a[]) {
    left[t] = l, right[t] = r;
    if (l == r) {
      sf[t][0] = a[l], sf[t][1] = 0;
    } else {
      int mid = (l + r) >> 1;
      build(t << 1, l, mid, a);
      build(t << 1 | 1, mid + 1, r, a);
      pushUp(t);
    }
  }
  void updata(int t, int p, int c) {
    if (left[t] == right[t]) {
      sf[t][0] = c, sf[t][1] = 0;
      return;
    }
    int mid = (left[t] + right[t]) >> 1;
    if (p <= mid)
      updata(t << 1, p, c);
    else
      updata(t << 1 | 1, p, c);
    pushUp(t);
  }
  pair<long long, long long> query(int t, int l, int r) {
    if (left[t] == l && right[t] == r) {
      return make_pair(sf[t][0], sf[t][1]);
    }
    int mid = (left[t] + right[t]) >> 1;
    if (r <= mid)
      return query(t << 1, l, r);
    else if (l > mid)
      return query(t << 1 | 1, l, r);
    else {
      pair<long long, long long> t1 = query(t << 1, l, mid);
      pair<long long, long long> t2 = query(t << 1 | 1, mid + 1, r);
      int len = mid - l + 1;
      t1.second += t2.first * mat[len].c[0][1] % mod;
      t1.second %= mod;
      t1.second += t2.second * mat[len].c[1][1] % mod;
      t1.second %= mod;
      t1.first += t2.first * mat[len].c[0][0] % mod;
      t1.first %= mod;
      t1.first += t2.second * mat[len].c[1][0] % mod;
      t1.first %= mod;
      return t1;
    }
  }
} seg;
int a[maxn], n, m;
int main() {
  scanf("%d %d", &n, &m);
  init(n);
  for (int i = 0; i < n; ++i) {
    scanf("%d", &a[i]);
  }
  seg.build(1, 0, n - 1, a);
  for (int i = 0; i < m; ++i) {
    int t;
    scanf("%d", &t);
    if (t == 1) {
      int x, v;
      scanf("%d %d", &x, &v);
      seg.updata(1, x - 1, v);
    } else if (t == 2) {
      int l, r;
      scanf("%d %d", &l, &r);
      --l, --r;
      pair<long long, long long> t = seg.query(1, l, r);
      t.first = (t.first % mod + mod) % mod;
      printf("%I64d\n", t.first);
    } else if (t == 3) {
    }
  }
  return 0;
}
