#include <bits/stdc++.h>
#pragma comment(linker, "/STACK:128777216")
const int null = 0;
using namespace std;
template <class T>
int size(const T &a) {
  return int(a.size());
}
template <class T>
T abs(const T &a) {
  return (a < 0 ? -a : a);
}
template <class T>
T sqr(const T &a) {
  return a * a;
}
const int max_n = 200010, mod = 1000000000;
struct V {
  long long f1, f2;
  void init(int f1, int f2) {
    if (f1 < 0) {
      f1 += mod;
    }
    if (f2 < 0) {
      f2 += mod;
    }
    if (f1 >= mod) {
      f1 -= mod;
    }
    if (f2 >= mod) {
      f2 -= mod;
    }
    this->f1 = f1;
    this->f2 = f2;
  }
  void addf1(int x) {
    f1 += x;
    if (f1 >= mod) {
      f1 -= mod;
    }
  }
  void addf2(int x) {
    f2 += x;
    if (f2 >= mod) {
      f2 -= mod;
    }
  }
} ds[max_n], das[max_n];
int f[max_n];
struct Tree {
  V a[1 << 19];
  int n;
  void init(int n) { this->n = n; }
  void up(int i, int l, int mid, int r) {
    V &left = a[i + i], &right = a[i + i + 1];
    V &cur = a[i];
    V &ds0 = ds[r - mid], ds1 = ds[r - mid - 1];
    cur.init((ds0.f1 * left.f1 + ds1.f1 * left.f2 + right.f1) % mod,
             (ds0.f2 * left.f1 + ds1.f2 * left.f2 + right.f2) % mod);
  }
  void set(int i, int l, int r, int x, int val) {
    if (r - l == 1) {
      a[i].init(val, 0);
      return;
    }
    int mid = (l + r) >> 1;
    if (x < mid) {
      set(i + i, l, mid, x, val);
    } else {
      set(i + i + 1, mid, r, x, val);
    }
    up(i, l, mid, r);
  }
  void set(int x, int val) { set(1, 0, n, x, val); }
  int count(int i, int l, int r, int l2, int r2) {
    if (r <= l2 || r2 <= l) {
      return 0;
    }
    if (l2 <= l && r <= r2) {
      int index = r - 1 - l2;
      return (a[i].f1 * f[index] + a[i].f2 * f[index + 1]) % mod;
    }
    int mid = (l + r) >> 1;
    int res = count(i + i, l, mid, l2, r2) + count(i + i + 1, mid, r, l2, r2);
    if (res >= mod) {
      res -= mod;
    }
    return res;
  }
  int count(int l, int r) { return count(1, 0, n, l, r + 1); }
} tree;
int main() {
  int n, m;
  scanf("%d %d", &n, &m);
  ds[0].init(1, 0);
  ds[1].init(-1, 1);
  das[0].init(1, 0);
  das[1].init(0, 1);
  f[0] = f[1] = 1;
  for (int i = 2; i <= n; i++) {
    const V &p1 = ds[i - 1];
    const V &p2 = ds[i - 2];
    ds[i].init(p2.f1 - p1.f1, p2.f2 - p1.f2);
    das[i].init(ds[i].f1 + das[i - 1].f1, ds[i].f2 + das[i - 1].f2);
    f[i] = f[i - 1] + f[i - 2];
    if (f[i] >= mod) {
      f[i] -= mod;
    }
  }
  tree.init(n);
  for (int i = 0; i < n; i++) {
    int t;
    scanf("%d", &t);
    tree.set(i, t);
  }
  for (int i = 0; i < m; i++) {
    int t, a, b;
    scanf("%d %d %d", &t, &a, &b);
    switch (t) {
      case 1:
        tree.set(a - 1, b);
        break;
      case 2:
        printf("%d\n", tree.count(a - 1, b - 1));
        break;
      case 3:
        break;
    }
  }
  return 0;
}
