#include <bits/stdc++.h>
using namespace std;
const int N = 200000 + 10;
const int MOD = 1e9;
int f[N], sum[N], sum2[N];
int v[N];
struct Node {
  int a, b;
  int x, y;
  Node *left, *right;
  int delta;
};
Node pool[N << 2], *last = pool;
int A, B, C;
ostream &operator<<(ostream &out, const Node &cur) {
  out << "[" << cur.a << "," << cur.b << "): " << cur.x << "," << cur.y << ","
      << cur.delta;
  return out;
}
void build(Node *&cur, int a, int b) {
  cur = last++;
  cur->a = a;
  cur->b = b;
  cur->delta = 0;
  if (a + 1 == b) {
    cur->x = cur->y = v[a] % MOD;
    return;
  }
  build(cur->left, a, (a + b) / 2);
  build(cur->right, (a + b) / 2, b);
  int len = (a + b) / 2 - a;
  cur->x = (cur->left->x + (long long)f[len - 1] * cur->right->x +
            (long long)f[len] * cur->right->y) %
           MOD;
  cur->y = (cur->left->y + (long long)f[len] * cur->right->x +
            (long long)f[len + 1] * cur->right->y) %
           MOD;
}
void pass(Node *cur) {
  if (cur->delta == 0) return;
  Node *left = cur->left;
  Node *right = cur->right;
  left->delta = (left->delta + cur->delta) % MOD;
  left->x = (left->x + (long long)sum[left->b - left->a] * cur->delta) % MOD;
  left->y =
      (left->y + (long long)sum2[left->b - left->a + 1] * cur->delta) % MOD;
  right->delta = (right->delta + cur->delta) % MOD;
  right->x =
      (right->x + (long long)sum[right->b - right->a] * cur->delta) % MOD;
  right->y =
      (right->y + (long long)sum2[right->b - right->a + 1] * cur->delta) % MOD;
  cur->delta = 0;
}
void assign(Node *cur) {
  if (cur->a + 1 == cur->b) {
    cur->x = cur->y = B % MOD;
    return;
  }
  pass(cur);
  if (A < (cur->a + cur->b) / 2)
    assign(cur->left);
  else
    assign(cur->right);
  int len = (cur->a + cur->b) / 2 - cur->a;
  cur->x = (cur->left->x + (long long)f[len - 1] * cur->right->x +
            (long long)f[len] * cur->right->y) %
           MOD;
  cur->y = (cur->left->y + (long long)f[len] * cur->right->x +
            (long long)f[len + 1] * cur->right->y) %
           MOD;
}
void update(Node *cur) {
  if (cur->a >= A && cur->b <= B) {
    cur->delta = (cur->delta + C) % MOD;
    cur->x = (cur->x + (long long)sum[cur->b - cur->a] * C) % MOD;
    cur->y = (cur->y + (long long)sum2[cur->b - cur->a + 1] * C) % MOD;
    return;
  }
  pass(cur);
  if ((cur->a + cur->b) / 2 > A) update(cur->left);
  if ((cur->a + cur->b) / 2 < B) update(cur->right);
  int len = (cur->a + cur->b) / 2 - cur->a;
  cur->x = (cur->left->x + (long long)f[len - 1] * cur->right->x +
            (long long)f[len] * cur->right->y) %
           MOD;
  cur->y = (cur->left->y + (long long)f[len] * cur->right->x +
            (long long)f[len + 1] * cur->right->y) %
           MOD;
}
int query(Node *cur) {
  if (cur->a >= A && cur->b <= B) {
    if (cur->a == A) return cur->x;
    return ((long long)f[cur->a - A - 1] * cur->x +
            (long long)f[cur->a - A] * cur->y) %
           MOD;
  }
  int ret = 0;
  pass(cur);
  if ((cur->a + cur->b) / 2 > A) ret = (ret + query(cur->left)) % MOD;
  if ((cur->a + cur->b) / 2 < B) ret = (ret + query(cur->right)) % MOD;
  return ret;
}
void print(Node *cur, int dep) {
  for (int i = 0; i < dep; ++i) putchar(' ');
  cout << *cur << endl;
  if (cur->a + 1 == cur->b) return;
  print(cur->left, dep + 1);
  print(cur->right, dep + 1);
}
int main() {
  int n, m;
  scanf("%d %d", &n, &m);
  f[0] = 0;
  f[1] = 1;
  for (int i = 2; i <= n; ++i) {
    f[i] = (f[i - 1] + f[i - 2]) % MOD;
  }
  sum[0] = 0;
  for (int i = 1; i <= n; ++i) {
    sum[i] = (sum[i - 1] + f[i]) % MOD;
  }
  sum2[0] = sum2[1] = 0;
  for (int i = 2; i <= n; ++i) {
    sum2[i] = (sum[i] + MOD - 1) % MOD;
  }
  for (int i = 0; i < n; ++i) scanf("%d", v + i);
  Node *root;
  build(root, 0, n);
  while (m--) {
    int t;
    scanf("%d", &t);
    if (t == 1) {
      scanf("%d %d", &A, &B);
      --A;
      assign(root);
    } else if (t == 2) {
      scanf("%d %d", &A, &B);
      --A;
      printf("%d\n", query(root));
    } else {
      scanf("%d %d %d", &A, &B, &C);
      --A;
      update(root);
    }
  }
  return 0;
}
