#include <bits/stdc++.h>
using namespace std;
int n, m, in[200005], same[200005 * 4];
long long s0[200005 * 4], s1[200005 * 4], fib[200005];
long long f(long long f0, long long f1, int x) {
  if (x == 0) return f0;
  x -= 1;
  long long mat[2][2] = {{f1, f0}, {f0, 0}};
  long long mat2[2][2] = {{1, 1}, {1, 0}};
  long long mat3[2][2];
  while (x) {
    if (x & 1) {
      memset(mat3, 0, sizeof(mat3));
      for (int i = 0; i <= 1; i++)
        for (int j = 0; j <= 1; j++)
          for (int k = 0; k <= 1; k++) {
            mat3[i][j] += mat[i][k] * mat2[k][j];
            mat3[i][j] %= 1000000000;
          }
      memcpy(mat, mat3, sizeof(mat3));
    }
    memset(mat3, 0, sizeof(mat3));
    for (int i = 0; i <= 1; i++)
      for (int j = 0; j <= 1; j++)
        for (int k = 0; k <= 1; k++) {
          mat3[i][j] += mat2[i][k] * mat2[k][j];
          mat3[i][j] %= 1000000000;
        }
    memcpy(mat2, mat3, sizeof(mat3));
    x >>= 1;
  }
  return mat[0][0];
}
long long fibsum(int l, int r) {
  long long re = fib[r];
  if (l) re -= fib[l - 1];
  re = (re % 1000000000 + 1000000000) % 1000000000;
  return re;
}
void upd(int cur, int ll, int rr) {
  if (ll == rr) return;
  int mid = (ll + rr) >> 1;
  s0[cur] = s0[(cur << 1)] +
            f(s0[((cur << 1) + 1)], s1[((cur << 1) + 1)], mid - ll + 1);
  s1[cur] = s1[(cur << 1)] +
            f(s0[((cur << 1) + 1)], s1[((cur << 1) + 1)], mid - ll + 2);
  s0[cur] %= 1000000000;
  s1[cur] %= 1000000000;
}
void init(int cur, int ll, int rr) {
  if (ll == rr) {
    s0[cur] = s1[cur] = in[ll];
    return;
  }
  int mid = (ll + rr) >> 1;
  init((cur << 1), ll, mid);
  init(((cur << 1) + 1), mid + 1, rr);
  upd(cur, ll, rr);
}
void fix(int cur, int ll, int rr, int x, int v) {
  if (ll == rr) {
    s0[cur] = s1[cur] = v;
    return;
  }
  int mid = (ll + rr) >> 1;
  if (x <= mid)
    fix((cur << 1), ll, mid, x, v);
  else
    fix(((cur << 1) + 1), mid + 1, rr, x, v);
  upd(cur, ll, rr);
}
long long query(int cur, int ll, int rr, int l, int r, int lf) {
  if (ll == l && rr == r) return f(s0[cur], s1[cur], ll - lf);
  int mid = (ll + rr) >> 1;
  if (r <= mid)
    return query((cur << 1), ll, mid, l, r, lf);
  else if (l > mid)
    return query(((cur << 1) + 1), mid + 1, rr, l, r, lf);
  return (query((cur << 1), ll, mid, l, mid, lf) +
          query(((cur << 1) + 1), mid + 1, rr, mid + 1, r, lf)) %
         1000000000;
}
int main() {
  int x, y, z;
  fib[0] = fib[1] = 1;
  for (int i = 2; i <= 200005 - 1; i++)
    fib[i] = (fib[i - 1] + fib[i - 2]) % 1000000000;
  for (int i = 1; i <= 200005 - 1; i++)
    fib[i] = (fib[i] + fib[i - 1]) % 1000000000;
  while (~scanf("%d %d", &n, &m)) {
    for (int i = 1; i <= n; i++) scanf("%d", &in[i]);
    init(1, 1, n);
    while (m--) {
      scanf("%d", &z);
      if (z == 1) {
        scanf("%d %d", &x, &y);
        fix(1, 1, n, x, y);
      } else if (z == 2) {
        scanf("%d %d", &x, &y);
        printf("%I64d\n", query(1, 1, n, x, y, x));
      }
    }
  }
  return 0;
}
