#include <bits/stdc++.h>
using namespace std;
#pragma comment(linker, "/STACK:16000000")
const int INF = 1e9;
const double EPS = 1e-8;
const double PI = 2 * acos(0.);
const int P = 1000 * 1000 * 1000;
const int T = 1 << 18;
int a[200500];
long long f[200500];
int rsq[2][2 * T];
void set_value(int k, int pos, int val) {
  pos += T;
  rsq[k][pos] = val % P;
  while (pos > 1) {
    pos /= 2;
    rsq[k][pos] = (rsq[k][pos * 2] + rsq[k][pos * 2 + 1]) % P;
  }
}
int get_sum(int k, int l, int r) {
  l += T;
  r += T;
  int ans = 0;
  while (l <= r) {
    if (l & 1) ans = (ans + rsq[k][l]) % P;
    if (!(r & 1)) ans = (ans + rsq[k][r]) % P;
    l = (l + 1) / 2;
    r = (r - 1) / 2;
  }
  return ans;
}
int main() {
  int n, m;
  scanf("%d%d", &n, &m);
  for (int i = 0; i < n; ++i) {
    scanf("%d", &a[i]);
  }
  f[0] = 1;
  f[1] = 1;
  for (int i = 2; i <= n; ++i) {
    f[i] = (f[i - 1] + f[i - 2]) % P;
  }
  for (int i = 0; i < n; ++i) {
    set_value(0, i, f[i] * a[i] % P);
    if (i > 0) set_value(1, i, f[i - 1] * a[i] % P);
  }
  for (int i = 0; i < m; ++i) {
    int t;
    scanf("%d", &t);
    if (t == 1) {
      int x, v;
      scanf("%d%d", &x, &v);
      --x;
      set_value(0, x, f[x] * v % P);
      if (x > 0) set_value(1, x, f[x - 1] * v % P);
    } else {
      int l, r;
      scanf("%d%d", &l, &r);
      --l;
      --r;
      int s1 = get_sum(0, l, r);
      int s2 = get_sum(1, l, r);
      cerr << s1 << " " << s2;
      long long ans = 0;
      if (l == 0)
        ans = s1;
      else if (l == 1)
        ans = s2;
      else if (l & 1)
        ans = f[l - 1] * s2 - f[l - 2] * s1;
      else
        ans = f[l - 2] * s1 - f[l - 1] * s2;
      printf("%I64d\n", (ans % P + P) % P);
    }
  }
  return 0;
}
