#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2000 * 100 + 5;
const long long mod = 1000 * 1000 * 1000;
struct Node {
  long long v1, v2;
};
Node tree[MAXN * 4];
long long fibnumb[MAXN];
long long fibsum[MAXN];
long long arr[MAXN];
void build(int v, int l, int r) {
  for (int i = l, j = 0; i <= r; i++, j++) {
    tree[v].v1 = (tree[v].v1 + fibnumb[j] * arr[i]) % mod;
    tree[v].v2 = (tree[v].v2 + fibnumb[j + 1] * arr[i]) % mod;
  }
  if (l == r) return;
  int mid = (l + r) / 2;
  build(v * 2, l, mid);
  build(v * 2 + 1, mid + 1, r);
}
long long calc(long long v1, long long v2, int offset) {
  if (offset == 0) return v1;
  if (offset == 1) return v2;
  return (v1 * fibnumb[offset - 2] + v2 * fibnumb[offset - 1]) % mod;
}
long long range_get(int v, int l, int r, int a, int b, int offset = 0) {
  if (l == a && r == b) return calc(tree[v].v1, tree[v].v2, offset);
  int mid = (l + r) / 2;
  long long ans = 0;
  if (a <= mid)
    ans = (ans + range_get(v * 2, l, mid, a, min(mid, b), offset)) % mod;
  if (b > mid)
    ans = (ans + range_get(v * 2 + 1, mid + 1, r, max(a, mid + 1), b,
                           offset + max(0, mid - a + 1))) %
          mod;
  return ans;
}
void set_val(int v, int l, int r, int pos, long long newval, long long oldval) {
  tree[v].v1 =
      (tree[v].v1 + ((newval - oldval + mod) * fibnumb[pos - l])) % mod;
  tree[v].v2 =
      (tree[v].v2 + ((newval - oldval + mod) * fibnumb[pos - l + 1])) % mod;
  if (l == r) return;
  int mid = (l + r) / 2;
  if (pos <= mid)
    set_val(v * 2, l, mid, pos, newval, oldval);
  else
    set_val(v * 2 + 1, mid + 1, r, pos, newval, oldval);
}
int main() {
  fibnumb[0] = fibsum[0] = fibnumb[1] = 1;
  fibsum[1] = 2;
  for (int i = 2; i < MAXN; i++) {
    fibnumb[i] = (fibnumb[i - 1] + fibnumb[i - 2]) % mod;
    fibsum[i] = (fibsum[i - 1] + fibnumb[i]);
  }
  int n, m;
  cin >> n >> m;
  for (int i = 0; i < n; i++) {
    int t;
    scanf("%d", &t);
    arr[i] = t;
  }
  build(1, 0, n - 1);
  for (int i = 0; i < m; i++) {
    int command;
    scanf("%d", &command);
    switch (command) {
      case 1:
        int x, v;
        scanf("%d%d", &x, &v);
        x--;
        set_val(1, 0, n - 1, x, v, arr[x]);
        arr[x] = v;
        break;
      case 2:
        int l, r;
        scanf("%d%d", &l, &r);
        long long ans = range_get(1, 0, n - 1, l - 1, r - 1);
        cout << ans << endl;
        break;
    }
  }
  return 0;
}
