#include <bits/stdc++.h>
using namespace std;
#pragma comment(linker, "/STACK:200000000")
const double EPS = 1E-9;
const int INF = 1000000000;
const long long INF64 = (long long)1E18;
const double PI = 3.1415926535897932384626433832795;
const int NMAX = 810000;
const long long MOD = INF;
long long a[NMAX], f[NMAX], md[NMAX][2], rel[NMAX], sum[NMAX];
inline long long get(int idx, int s) {
  if (s <= 1) return md[idx][s];
  return (md[idx][0] * f[s - 2] + md[idx][1] * f[s - 1]) % MOD;
}
inline void calc(int idx, int l, int r) {
  int mid = (l + r) >> 1;
  md[idx][0] = (md[idx << 1][0] + get(idx << 1 | 1, mid + 1 - l)) % MOD;
  md[idx][1] = (md[idx << 1][1] + get(idx << 1 | 1, mid + 2 - l)) % MOD;
}
inline void relax(int idx, int l, int r) {
  if (rel[idx]) {
    md[idx][0] = (md[idx][0] + sum[r - l] * rel[idx]) % MOD;
    md[idx][1] = (md[idx][1] + (sum[r - l + 1] - 1 + MOD) * rel[idx]) % MOD;
    if (l != r) {
      rel[idx << 1] = (rel[idx << 1] + rel[idx]) % MOD;
      rel[idx << 1 | 1] = (rel[idx << 1 | 1] + rel[idx]) % MOD;
    }
    rel[idx] = 0;
  }
}
void build(int idx, int l, int r) {
  if (l == r) {
    md[idx][0] = md[idx][1] = a[l];
    return;
  }
  int mid = (l + r) >> 1;
  build(idx << 1, l, mid);
  build(idx << 1 | 1, mid + 1, r);
  calc(idx, l, r);
}
long long get(int idx, int l, int r, int a, int b) {
  relax(idx, l, r);
  if (b < l || r < a) return 0;
  if (a <= l && r <= b) return get(idx, l - a);
  int mid = (l + r) >> 1;
  long long res = 0;
  res += get(idx << 1, l, mid, a, b);
  res += get(idx << 1 | 1, mid + 1, r, a, b);
  res %= MOD;
  calc(idx, l, r);
  return res;
}
void assign(int idx, int l, int r, int pos, int val) {
  relax(idx, l, r);
  if (pos < l || r < pos) return;
  if (l == r) {
    md[idx][0] = md[idx][1] = val;
    return;
  }
  int mid = (l + r) >> 1;
  assign(idx << 1, l, mid, pos, val);
  assign(idx << 1 | 1, mid + 1, r, pos, val);
  calc(idx, l, r);
}
void update(int idx, int l, int r, int a, int b, int val) {
  relax(idx, l, r);
  if (b < l || r < a) return;
  if (a <= l && r <= b) {
    rel[idx] = val;
    return relax(idx, l, r);
  }
  int mid = (l + r) >> 1;
  update(idx << 1, l, mid, a, b, val);
  update(idx << 1 | 1, mid + 1, r, a, b, val);
  calc(idx, l, r);
}
int main() {
  int n, m;
  cin >> n >> m;
  for (int i = 0; i < (int)(n); i++) {
    int val;
    scanf("%d", &val);
    a[i] = val;
  }
  f[0] = f[1] = 1;
  sum[0] = 1;
  sum[1] = 2;
  for (int i = 2; i < NMAX; i++) {
    f[i] = (f[i - 2] + f[i - 1]) % MOD;
    sum[i] = (sum[i - 1] + f[i]) % MOD;
  }
  build(1, 0, n - 1);
  for (int ii = 0; ii < (int)(m); ii++) {
    int tp;
    scanf("%d", &tp);
    if (tp == 1) {
      int x, v;
      scanf("%d%d", &x, &v);
      x--;
      assign(1, 0, n - 1, x, v);
    } else if (tp == 2) {
      int l, r;
      scanf("%d%d", &l, &r);
      l--;
      r--;
      int res = (int)get(1, 0, n - 1, l, r);
      printf("%d\n", res);
    } else {
      int l, r, v;
      scanf("%d%d%d", &l, &r, &v);
      l--;
      r--;
      update(1, 0, n - 1, l, r, v);
    }
  }
  return 0;
}
