#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9;
const int SIZE = 1e6 + 10;
const int MATRIX_SIZE = 2;
struct Matrix_Power {
  long long AA[60][MATRIX_SIZE][MATRIX_SIZE], aa[62][MATRIX_SIZE];
  int N;
  void set(long long _A[][MATRIX_SIZE], int _N,
           long long bb = (long long)1e18) {
    N = _N;
    for (int i = 0; i < (N); ++i)
      for (int j = 0; j < (N); ++j) AA[0][i][j] = _A[i][j];
    for (int round = (1); round < (60); ++round) {
      if ((1LL << round) > bb) break;
      for (int i = 0; i < (N); ++i)
        for (int j = 0; j < (N); ++j) AA[round][i][j] = 0;
      for (int i = 0; i < (N); ++i)
        for (int j = 0; j < (N); ++j)
          for (int k = 0; k < (N); ++k) {
            AA[round][i][k] += AA[round - 1][i][j] * AA[round - 1][j][k];
            AA[round][i][k] %= MOD;
          }
    }
  }
  long long get(long long _a[], long long v) {
    memset((aa), 0, sizeof((aa)));
    for (int i = 0; i < (N); ++i) aa[0][i] = _a[i];
    for (int i = 0; i < (61); ++i) {
      if ((1LL << i) > v) return aa[i][N - 1];
      if ((v >> i) & 1) {
        for (int j = 0; j < (N); ++j)
          for (int k = 0; k < (N); ++k) {
            aa[i + 1][j] += AA[i][j][k] * aa[i][k];
            aa[i + 1][j] %= MOD;
          }
      } else
        for (int j = 0; j < (N); ++j) aa[i + 1][j] = aa[i][j];
    }
    return -1;
  }
} Mat;
long long A[2][MATRIX_SIZE];
long long aa[SIZE];
long long fib[2][SIZE];
long long a[SIZE];
void ADD(long long &x, long long v) { x = (x + v) % MOD; }
struct SegTree {
  int lv;
  int num[SIZE];
  long long sum[SIZE], p[SIZE], fib_sum[SIZE];
  int ll, rr, N;
  long long v;
  void push(int id, int st) {
    if (!p[id]) return;
    ADD(sum[id], fib_sum[id] * p[id]);
    if (num[id] != 1) {
      ADD(p[id * 2], p[id]);
      ADD(p[id * 2 + 1], p[id]);
    }
    p[id] = 0;
  }
  void __init(int L, int R, int id) {
    p[id] = 0;
    if (L == R) {
      num[id] = 1;
      sum[id] = a[L] * fib[lv][L] % MOD;
      fib_sum[id] = fib[lv][L];
      return;
    }
    int mm = (L + R) >> 1;
    __init(L, mm, id * 2);
    __init(mm + 1, R, id * 2 + 1);
    sum[id] = (sum[id * 2] + sum[id * 2 + 1]) % MOD;
    num[id] = num[id * 2] + num[id * 2 + 1];
    fib_sum[id] = (fib_sum[id * 2] + fib_sum[id * 2 + 1]) % MOD;
  }
  void init(int _N, int _lv) {
    lv = _lv;
    N = _N;
    __init(0, N, 1);
  }
  void __upd(int L, int R, int id) {
    push(id, L);
    if (L > rr || R < ll) return;
    if (L >= ll && R <= rr) {
      p[id] = v;
      push(id, L);
      return;
    }
    int mm = (L + R) >> 1;
    __upd(L, mm, id * 2);
    __upd(mm + 1, R, id * 2 + 1);
    sum[id] = (sum[id * 2] + sum[id * 2 + 1]) % MOD;
  }
  void upd(int _x, int _y, int _v) {
    ll = _x;
    rr = _y, v = _v;
    __upd(0, N, 1);
  }
  void __upd2(int L, int R, int id) {
    push(id, L);
    if (L > ll || R < ll) return;
    if (L == R) {
      sum[id] = v * fib[lv][L] % MOD;
      return;
    }
    int mm = (L + R) >> 1;
    __upd2(L, mm, id * 2);
    __upd2(mm + 1, R, id * 2 + 1);
    sum[id] = (sum[id * 2] + sum[id * 2 + 1]) % MOD;
  }
  void upd2(int _x, int _v) {
    ll = _x;
    v = _v;
    __upd2(0, N, 1);
  }
  long long __qq(int L, int R, int id) {
    if (L > rr || R < ll) return 0;
    push(id, L);
    if (L >= ll && R <= rr) return sum[id];
    int mm = (L + R) >> 1;
    return (__qq(L, mm, id * 2) + __qq(mm + 1, R, id * 2 + 1)) % MOD;
  }
  long long qq(int _x, int _y) {
    ll = _x;
    rr = _y;
    return __qq(0, N, 1);
  }
} seg[2];
int main() {
  A[0][1] = 1;
  A[1][0] = 1;
  A[1][1] = MOD - 1;
  Mat.set(A, 2, 1e7);
  int N, Q;
  scanf("%d%d", &N, &Q);
  fib[0][1] = fib[1][0] = fib[1][1] = 1;
  for (int i = (2); i < (N + 1); ++i) {
    for (int j = 0; j < (2); ++j)
      fib[j][i] = (fib[j][i - 2] + fib[j][i - 1]) % MOD;
  }
  for (int i = (1); i < (N + 1); ++i) scanf("%I64d", &a[i]);
  for (int i = 0; i < (2); ++i) seg[i].init(N, i);
  while (Q--) {
    int(ty);
    scanf("%d", &ty);
    if (ty == 1) {
      int x, v;
      scanf("%d%d", &x, &v);
      for (int i = 0; i < (2); ++i) seg[i].upd2(x, v);
    } else if (ty == 2) {
      int x, y;
      scanf("%d%d", &x, &y);
      aa[1] = seg[0].qq(x, y);
      aa[0] = seg[1].qq(x, y);
      printf("%I64d\n", Mat.get(aa, x - 1));
    } else {
      int x, y, v;
      scanf("%d%d%d", &x, &y, &v);
      for (int i = 0; i < (2); ++i) seg[i].upd(x, y, v);
    }
  }
  return 0;
}
