#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200005;
const long long MOD = 1000000000LL;
long long sum[2][MAXN << 2], add[MAXN << 2], f[MAXN], s[MAXN];
int n, m, k;
void push_up(int rt, int m) {
  int k = m - (m >> 1);
  sum[0][rt] = (sum[0][rt << 1] + (f[k - 1] * sum[1][rt << 1 | 1]) % MOD +
                ((k == 1 ? 0 : f[k - 2]) * sum[0][rt << 1 | 1]) % MOD) %
               MOD;
  sum[1][rt] = (sum[1][rt << 1] + (f[k] * sum[1][rt << 1 | 1]) % MOD +
                (f[k - 1] * sum[0][rt << 1 | 1]) % MOD) %
               MOD;
}
void Add(int rt, int m, int c) {
  sum[0][rt] += s[m - 1] * c;
  sum[0][rt] %= MOD;
  sum[1][rt] += (s[m] - 1) * c;
  sum[1][rt] %= MOD;
}
void push_down(int rt, int m) {
  if (add[rt]) {
    add[rt << 1] = add[rt << 1 | 1] = add[rt];
    Add(rt << 1, m - (m >> 1), add[rt]);
    Add(rt << 1 | 1, m >> 1, add[rt]);
    add[rt] = 0;
  }
}
void build(int l = 1, int r = n, int rt = 1) {
  add[rt] = 0;
  if (l == r) {
    scanf("%I64d", &sum[0][rt]);
    sum[1][rt] = sum[0][rt];
    return;
  }
  int m = (l + r) >> 1;
  build(l, m, rt << 1);
  build(m + 1, r, rt << 1 | 1);
  push_up(rt, r - l + 1);
}
void cover(int p, int x, int l = 1, int r = n, int rt = 1) {
  if (l == r) {
    sum[0][rt] = sum[1][rt] = x;
    return;
  }
  push_down(rt, r - l + 1);
  int m = (l + r) >> 1;
  if (p > m)
    cover(p, x, m + 1, r, rt << 1 | 1);
  else
    cover(p, x, l, m, rt << 1);
  push_up(rt, r - l + 1);
}
void update(int L, int R, int c, int l = 1, int r = n, int rt = 1) {
  if (L <= l && r <= R) {
    Add(rt, r - l + 1, c);
    add[rt] = c;
    return;
  }
  push_down(rt, r - l + 1);
  int m = (l + r) >> 1;
  if (L <= m) update(L, R, c, l, m, rt << 1);
  if (R > m) update(L, R, c, m + 1, r, rt << 1 | 1);
  push_up(rt, r - l + 1);
}
long long query(int L, int R, int l = 1, int r = n, int rt = 1) {
  if (L <= l && r <= R) {
    long long ret;
    if (k == 0)
      ret = sum[0][rt];
    else if (k == 1)
      ret = sum[1][rt];
    else
      ret = (f[k - 1] * sum[1][rt] % MOD + f[k - 2] * sum[0][rt] % MOD) % MOD;
    k += r - l + 1;
    return ret % MOD;
  }
  push_down(rt, r - l + 1);
  long long ret = 0;
  int m = (l + r) >> 1;
  if (L <= m) ret += query(L, R, l, m, rt << 1);
  if (R > m) ret += query(L, R, m + 1, r, rt << 1 | 1);
  return ret % MOD;
}
int main() {
  scanf("%d%d", &n, &m);
  f[0] = f[1] = 1;
  s[0] = 1;
  s[1] = 2;
  for (int i = 2; i <= n; ++i) {
    f[i] = (f[i - 1] + f[i - 2]) % MOD;
    s[i] = (s[i - 1] + f[i]) % MOD;
  }
  build();
  while (m--) {
    int t, x, v, l, r, d;
    scanf("%d", &t);
    if (t == 1) {
      scanf("%d%d", &x, &v);
      cover(x, v);
    } else if (t == 2) {
      scanf("%d%d", &l, &r);
      k = 0;
      printf("%I64d\n", query(l, r));
    } else {
      scanf("%d%d%d", &l, &r, &d);
      update(l, r, d);
    }
  }
  return 0;
}
