#include <bits/stdc++.h>
const int MAX_N = 200000;
const int MOD = 1000000000;
struct Info {
  int sum[2];
};
struct Node {
  int l, r;
  Node *left, *right;
  Info info;
  int inc;
};
Node tree[MAX_N * 2 + 10], *root;
int tn, data[MAX_N + 10];
int n, m;
int f[MAX_N + 10][2], fsum[MAX_N + 10][2];
void init() {
  f[0][0] = 1;
  f[1][1] = 1;
  for (int j = 0; j < 2; j++)
    for (int i = 2; i <= n; i++) {
      f[i][j] = f[i - 1][j] + f[i - 2][j];
      if (f[i][j] >= MOD) f[i][j] -= MOD;
    }
  fsum[0][0] = 1;
  for (int j = 0; j < 2; j++)
    for (int i = 1; i <= n; i++) {
      fsum[i][j] = fsum[i - 1][j] + f[i][j];
      if (fsum[i][j] >= MOD) fsum[i][j] -= MOD;
    }
}
inline void inc(int& a, int b) {
  a += b;
  if (a >= MOD) a -= MOD;
}
Info merge(const Info& a, const Info& b, int len) {
  Info res = a;
  inc(res.sum[0], (int)((long long)f[len][0] * b.sum[0] % MOD));
  inc(res.sum[0], (int)((long long)f[len + 1][0] * b.sum[1] % MOD));
  inc(res.sum[1], (int)((long long)f[len][1] * b.sum[0] % MOD));
  inc(res.sum[1], (int)((long long)f[len + 1][1] * b.sum[1] % MOD));
  return res;
}
Node* build(int l, int r) {
  Node* cur = tree + (tn++);
  cur->l = l;
  cur->r = r;
  cur->inc = 0;
  if (l == r) {
    cur->info.sum[0] = data[l];
    cur->info.sum[1] = 0;
  } else {
    int mid = (l + r) >> 1;
    cur->left = build(l, mid);
    cur->right = build(mid + 1, r);
    cur->info = merge(cur->left->info, cur->right->info, mid - l + 1);
  }
  return cur;
}
inline void update(Node* cur, int incc) {
  inc(cur->inc, incc);
  inc(cur->info.sum[0],
      (int)((long long)fsum[cur->r - cur->l][0] * incc % MOD));
  inc(cur->info.sum[1],
      (int)((long long)fsum[cur->r - cur->l][1] * incc % MOD));
}
inline void pushDown(Node* cur) {
  if (cur->inc != 0) {
    update(cur->left, cur->inc);
    update(cur->right, cur->inc);
    cur->inc = 0;
  }
}
void change(Node* cur, int p, int v) {
  if (cur->l == cur->r) {
    cur->info.sum[0] = v;
    cur->info.sum[1] = 0;
    return;
  }
  pushDown(cur);
  int mid = (cur->l + cur->r) >> 1;
  if (p <= mid)
    change(cur->left, p, v);
  else
    change(cur->right, p, v);
  cur->info = merge(cur->left->info, cur->right->info, mid - cur->l + 1);
}
void change(Node* cur, int l, int r, int v) {
  if (cur->l == l && cur->r == r) {
    update(cur, v);
    return;
  }
  pushDown(cur);
  int mid = (cur->l + cur->r) >> 1;
  if (r <= mid)
    change(cur->left, l, r, v);
  else if (l > mid)
    change(cur->right, l, r, v);
  else {
    change(cur->left, l, mid, v);
    change(cur->right, mid + 1, r, v);
  }
  cur->info = merge(cur->left->info, cur->right->info, mid - cur->l + 1);
}
Info query(Node* cur, int l, int r) {
  if (cur->l == l && cur->r == r) return cur->info;
  pushDown(cur);
  int mid = (cur->l + cur->r) >> 1;
  if (r <= mid) return query(cur->left, l, r);
  if (l > mid) return query(cur->right, l, r);
  return merge(query(cur->left, l, mid), query(cur->right, mid + 1, r),
               mid - l + 1);
}
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) scanf("%d", data + i);
  init();
  root = build(1, n);
  Info res;
  int cmd;
  while (m--) {
    scanf("%d", &cmd);
    if (cmd == 1) {
      int x, v;
      scanf("%d%d", &x, &v);
      change(root, x, v);
    } else if (cmd == 2) {
      int l, r;
      scanf("%d%d", &l, &r);
      res = query(root, l, r);
      int ans = res.sum[0] + res.sum[1];
      if (ans >= MOD) ans -= MOD;
      printf("%d\n", ans);
    } else {
      int l, r, d;
      scanf("%d%d%d", &l, &r, &d);
      change(root, l, r, d);
    }
  }
  return 0;
}
