#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200005;
const int MOD = 1000000000;
int N, M;
long long f[MAXN], k[MAXN];
long long c[2][MAXN], fk[2][MAXN];
int getn() {
  int ret = 0;
  char c;
  while ((c = getchar()) < '0' || c > '9')
    ;
  while (c >= '0' && c <= '9') ret = ret * 10 + (c - '0'), c = getchar();
  return ret;
}
long long mod_mult(long long a, long long b, long long n) {
  long long ret = 0;
  int flag = (a > 0 && b < 0) || (a < 0 && b > 0) ? -1 : 1;
  a = abs(a), b = abs(b);
  while (b >= 1) {
    if (b & 1) {
      ret += a;
      if (ret >= n) ret -= n;
    }
    a = a << 1;
    if (a >= n) a -= n;
    b = b >> 1;
  }
  return (ret * flag + n) % n;
}
int lowbit(int x) { return x & -x; }
void add(int x, int d, int tar) {
  if (x <= 0) return;
  for (; x <= N; x += lowbit(x)) c[tar][x] += d;
}
long long sum(int x, int tar) {
  long long ans = 0;
  for (; x > 0; x -= lowbit(x)) ans += c[tar][x];
  return ans % MOD;
}
long long quick_pow(long long f0, long long f1, long long T) {
  long long ans[2][2] = {{1, 0}, {0, 1}};
  long long s[2][2] = {{-1, 1}, {1, 0}};
  long long temp[2][2];
  while (T >= 1) {
    if (T & 1) {
      memcpy(temp, ans, sizeof(ans));
      memset(ans, 0, sizeof(ans));
      for (int i = 0; i < 2; i++) {
        for (int j = 0; j < 2; j++) {
          for (int l = 0; l < 2; l++) {
            ans[i][j] = (ans[i][j] + (temp[i][l] * s[l][j]) % MOD) % MOD;
          }
        }
      }
    }
    memcpy(temp, s, sizeof(s));
    memset(s, 0, sizeof(s));
    for (int i = 0; i < 2; i++) {
      for (int j = 0; j < 2; j++) {
        for (int l = 0; l < 2; l++) {
          s[i][j] = (s[i][j] + (temp[i][l] * temp[l][j]) % MOD) % MOD;
        }
      }
    }
    T = (T >> 1);
  }
  return (mod_mult(ans[0][0], f1, MOD) + mod_mult(ans[0][1], f0, MOD)) % MOD;
}
int main() {
  f[1] = f[0] = 1;
  for (int i = 2; i < MAXN; i++) f[i] = (f[i - 1] + f[i - 2]) % MOD;
  while (scanf("%d%d", &N, &M) == 2) {
    memset(c, 0, sizeof(c));
    for (int i = 0; i < N; i++) {
      k[i] = getn();
      add(i + 1, (fk[0][i] = mod_mult(k[i], f[i], MOD)), 0);
      if (i != 0) add(i + 1, (fk[1][i] = mod_mult(k[i], f[i - 1], MOD)), 1);
    }
    for (int i = 0; i < M; i++) {
      int cmd = getn();
      if (cmd == 1) {
        int x = getn(), v = getn();
        k[x - 1] = v;
        add(x, -fk[0][x - 1], 0);
        fk[0][x - 1] = f[x - 1] * k[x - 1] % MOD;
        add(x, fk[0][x - 1], 0);
        if (x != 1) {
          add(x, -fk[1][x - 1], 1);
          fk[1][x - 1] = f[x - 2] * k[x - 1] % MOD;
          add(x, fk[1][x - 1], 1);
        }
      } else {
        int l = getn(), r = getn();
        long long f0 = sum(r, 0) - sum(l - 1, 0);
        long long f1 = sum(r, 1) - sum(l - 1, 1);
        long long ans;
        if (l == 1)
          ans = f0;
        else if (l == 2)
          ans = f1;
        else
          ans = quick_pow(f0, f1, l - 2);
        printf("%I64d\n", ans);
      }
    }
  }
  return 0;
}
