#include <bits/stdc++.h>
using namespace std;
struct node {
  int x, y;
  long long s[2];
} T[800005];
int n, m, op, x, y;
long long MOD = 1000000000;
long long F[200005];
long long query(int d, int x, int y, int off);
void cal(int d) {
  int l = T[d << 1].y - T[d << 1].x + 1;
  T[d].s[0] = (T[d << 1].s[0] + query((d << 1) + 1, T[d].x, T[d].y, l)) % MOD;
  T[d].s[1] =
      (T[d << 1].s[1] + query((d << 1) + 1, T[d].x, T[d].y, l + 1)) % MOD;
}
void build(int d, int x, int y) {
  T[d].x = x;
  T[d].y = y;
  if (x != y) {
    build(d << 1, x, (x + y) / 2);
    build(1 + (d << 1), (x + y) / 2 + 1, y);
    cal(d);
  } else {
    scanf("%I64d", &T[d].s[0]);
    T[d].s[1] = T[d].s[0];
  }
}
void update(int d, int x, int v) {
  if (T[d].x == T[d].y)
    T[d].s[0] = T[d].s[1] = v;
  else {
    if (x <= T[d << 1].y)
      update(d << 1, x, v);
    else
      update((d << 1) + 1, x, v);
    cal(d);
  }
}
long long query(int d, int x, int y, int off) {
  if (x <= T[d].x && y >= T[d].y) {
    if (off == 0) return T[d].s[0];
    if (off == 1) return T[d].s[1];
    return (T[d].s[0] * F[off - 2] + T[d].s[1] * F[off - 1]) % MOD;
  } else {
    long long res = 0;
    if (x <= T[d << 1].y) res += query(d << 1, x, y, off);
    if (y > T[d << 1].y) {
      if (x <= T[d << 1].y)
        res += query((d << 1) + 1, x, y,
                     off + T[(d << 1) + 1].x - max(x, T[d << 1].x));
      else
        res += query((d << 1) + 1, x, y, off);
    }
    return res % MOD;
  }
}
int main() {
  scanf("%d%d", &n, &m);
  F[0] = F[1] = 1;
  for (int i = (2); i <= (n); i++) F[i] = (F[i - 1] + F[i - 2]) % MOD;
  build(1, 1, n);
  while (m--) {
    scanf("%d%d%d", &op, &x, &y);
    if (op == 1) update(1, x, y);
    if (op == 2) printf("%d\n", (int)query(1, x, y, 0));
  }
  return 0;
}
