#include <bits/stdc++.h>
using namespace std;
const long long MAXN = 2e5 + 100, mod = 1e9;
long long ar[MAXN], fib[MAXN], N, M;
pair<long long, long long> seg[MAXN << 3];
long long calculate(long long i, long long st, long long nd) {
  if (!i) return st;
  if (i == 1) return nd;
  return ((st * fib[i - 2]) % mod + (nd * fib[i - 1]) % mod) % mod;
}
void init(long long k, long long b, long long e) {
  if (b == e) {
    seg[k].first = ar[b];
    seg[k].second = ar[b];
    return;
  }
  init(2 * k, b, (b + e) / 2);
  init(2 * k + 1, (b + e) / 2 + 1, e);
  seg[k].first = (calculate(0, seg[2 * k].first, seg[2 * k].second) +
                  calculate((b + e) / 2 - b + 1, seg[2 * k + 1].first,
                            seg[2 * k + 1].second)) %
                 mod;
  seg[k].second = (calculate(1, seg[2 * k].first, seg[2 * k].second) +
                   calculate((b + e) / 2 - b + 2, seg[2 * k + 1].first,
                             seg[2 * k + 1].second)) %
                  mod;
}
void update(long long k, long long b, long long e, long long x, long long t) {
  if (b > x or e < x) return;
  if (b == x and e == x) {
    seg[k].first = t;
    seg[k].second = t;
    return;
  }
  update(2 * k, b, (b + e) / 2, x, t);
  update(2 * k + 1, (b + e) / 2 + 1, e, x, t);
  seg[k].first = (calculate(0, seg[2 * k].first, seg[2 * k].second) +
                  calculate((b + e) / 2 - b + 1, seg[2 * k + 1].first,
                            seg[2 * k + 1].second)) %
                 mod;
  seg[k].second = (calculate(1, seg[2 * k].first, seg[2 * k].second) +
                   calculate((b + e) / 2 - b + 2, seg[2 * k + 1].first,
                             seg[2 * k + 1].second)) %
                  mod;
}
long long find(long long k, long long b, long long e, long long x,
               long long y) {
  if (b > y or e < x) return 0;
  if (b >= x and e <= y) return calculate(b - x, seg[k].first, seg[k].second);
  return (find(2 * k, b, (b + e) / 2, x, y) +
          find(2 * k + 1, (b + e) / 2 + 1, e, x, y)) %
         mod;
}
int main() {
  scanf("%lld%lld", &N, &M);
  fib[0] = fib[1] = 1;
  for (long long i = 2; i <= N; i++) fib[i] = (fib[i - 1] + fib[i - 2]) % mod;
  for (long long i = 1; i <= N; i++) scanf("%lld", &ar[i]);
  init(1, 1, N);
  for (long long i = 1, a, b, c; i <= M; i++) {
    scanf("%lld%lld%lld", &a, &b, &c);
    if (a == 1)
      update(1, 1, N, b, c);
    else
      printf("%lld\n", find(1, 1, N, b, c));
  }
  return 0;
}
