#include <bits/stdc++.h>
using namespace std;
const int N = 262144;
const long long MOD = 1000000000;
int n, in[N];
long long fib[N][2], fibSum[N];
class BSP {
 public:
  class Node {
   public:
    long long sum1, sum2, lazy;
    Node() : sum1(0), sum2(0), lazy(0) {}
  } tree[2 * N];
  long long calc(long long f1, long long f2, int m) {
    return (fib[m][0] * f1 + fib[m][1] * f2) % MOD;
  }
  Node update_node(int l1, int l2, Node lc, Node rc) {
    Node res;
    res.sum1 = (lc.sum1 + calc(rc.sum1, rc.sum2, l2 - l1 + 1)) % MOD;
    res.sum2 = (lc.sum2 + calc(rc.sum1, rc.sum2, l2 - l1 + 2)) % MOD;
    return res;
  }
  void push_down(int l1, int r1, int l2, int r2, Node &fa, Node &lc, Node &rc) {
    lc.sum1 = (lc.sum1 + (fibSum[r1 - l1 + 1]) * fa.lazy) % MOD;
    lc.sum2 = (lc.sum2 + (fibSum[r1 - l1 + 2] - 1) * fa.lazy) % MOD;
    rc.sum1 = (rc.sum1 + (fibSum[r2 - l2 + 1]) * fa.lazy) % MOD;
    rc.sum2 = (rc.sum2 + (fibSum[r2 - l2 + 2] - 1) * fa.lazy) % MOD;
    lc.lazy = (lc.lazy + fa.lazy) % MOD;
    rc.lazy = (rc.lazy + fa.lazy) % MOD;
    fa.lazy = 0;
  }
  void init_tree(int l, int r, int id) {
    tree[id].lazy = 0;
    if (l == r) {
      tree[id].sum1 = tree[id].sum2 = in[l];
      return;
    }
    int m = (l + r) / 2, lc = id * 2 + 1, rc = id * 2 + 2;
    init_tree(l, m, lc);
    init_tree(m + 1, r, rc);
    tree[id] = update_node(l, m + 1, tree[lc], tree[rc]);
  }
  void update(int l, int r, int fn, int val, int id) {
    if (l == r) {
      tree[id].sum1 = tree[id].sum2 = val;
      tree[id].lazy = 0;
      return;
    }
    int m = (l + r) / 2, lc = id * 2 + 1, rc = id * 2 + 2;
    if (tree[id].lazy) push_down(l, m, m + 1, r, tree[id], tree[lc], tree[rc]);
    if (fn <= m)
      update(l, m, fn, val, lc);
    else
      update(m + 1, r, fn, val, rc);
    tree[id] = update_node(l, m + 1, tree[lc], tree[rc]);
  }
  void update_plus(int l, int r, int fl, int fr, long long mul, int id) {
    if (l == fl && r == fr) {
      tree[id].sum1 = (tree[id].sum1 + fibSum[r - l + 1] * mul) % MOD;
      tree[id].sum2 = (tree[id].sum2 + (fibSum[r - l + 2] - 1) * mul) % MOD;
      tree[id].lazy += mul;
      return;
    }
    int m = (l + r) / 2, lc = id * 2 + 1, rc = id * 2 + 2;
    if (tree[id].lazy) push_down(l, m, m + 1, r, tree[id], tree[lc], tree[rc]);
    if (fr <= m)
      update_plus(l, m, fl, fr, mul, lc);
    else if (m < fl)
      update_plus(m + 1, r, fl, fr, mul, rc);
    else {
      update_plus(l, m, fl, m, mul, lc);
      update_plus(m + 1, r, m + 1, fr, mul, rc);
    }
    tree[id] = update_node(l, m + 1, tree[lc], tree[rc]);
  }
  Node query(int l, int r, int fl, int fr, int id) {
    if (l == fl && r == fr) return tree[id];
    int m = (l + r) / 2, lc = id * 2 + 1, rc = id * 2 + 2;
    if (tree[id].lazy) push_down(l, m, m + 1, r, tree[id], tree[lc], tree[rc]);
    if (fr <= m) return query(l, m, fl, fr, lc);
    if (m < fl) return query(m + 1, r, fl, fr, rc);
    return update_node(fl, m + 1, query(l, m, fl, m, lc),
                       query(m + 1, r, m + 1, fr, rc));
  }
} tree;
int main(int argc, char **argv) {
  fib[1][0] = 1;
  fib[2][1] = 1;
  fib[1][1] = fib[2][0] = 0;
  fibSum[1] = 1;
  fibSum[2] = 2;
  for (int i = 3; i < N; i++) {
    fib[i][0] = (fib[i - 1][0] + fib[i - 2][0]) % MOD;
    fib[i][1] = (fib[i - 1][1] + fib[i - 2][1]) % MOD;
    fibSum[i] = (fibSum[i - 1] + fib[i][0] + fib[i][1]) % MOD;
  }
  int nq;
  scanf("%d%d", &n, &nq);
  for (int i = 1; i <= n; i++) scanf("%d", &in[i]);
  tree.init_tree(1, n, 0);
  int cmd;
  while (nq--) {
    scanf("%d", &cmd);
    if (cmd == 1) {
      int l, v;
      scanf("%d%d", &l, &v);
      tree.update(1, n, l, v, 0);
    } else if (cmd == 2) {
      int l, r;
      scanf("%d%d", &l, &r);
      printf("%I64d\n", tree.query(1, n, l, r, 0).sum1);
    } else {
      int l, r, v;
      scanf("%d%d%d", &l, &r, &v);
      tree.update_plus(1, n, l, r, v, 0);
    }
  }
  return 0;
}
