#include <bits/stdc++.h>
#pragma comment(linker, "/stack:67108864")
using namespace std;
const long double EPS = 1e-9;
const long double PI = 3.1415926535897932384626433832795;
const long long INF = 1000 * 1000 * 1000 + 9;
const int NMAX = 100 + 300;
const int MMAX = 10000;
const int MOD = 1e9;
int n, m;
long long a[NMAX];
struct zz {
  int type;
  int first, second;
} z[MMAX];
inline bool read() {
  if (!(cin >> n >> m)) return false;
  for (int i = 0; i < int(n); ++i) {
    cin >> a[i];
  }
  for (int i = 0; i < int(m); ++i) {
    cin >> z[i].type >> z[i].first >> z[i].second;
  }
  return true;
}
inline void solve() {
  for (int i = 0; i < int(m); ++i) {
    if (z[i].type == 1)
      a[z[i].first - 1] = z[i].second;
    else {
      int lf = z[i].first, rg = z[i].second;
      lf--, rg--;
      long long f1 = 1, f2 = 1;
      long long ans = 0;
      for (int i = int(lf); i <= int(rg); ++i) {
        ans += f1 * a[i];
        int f3 = f1 + f2;
        f1 = f2;
        f2 = f3;
        ans %= MOD;
        f1 %= MOD;
        f2 %= MOD;
      }
      cout << ans << endl;
    }
  }
}
int main() {
  ifstream ifile("input.txt");
  if (ifile) {
    freopen("input.txt", "rt", stdin);
  }
  if (ifile) {
    freopen("output.txt", "wt", stdout);
  }
  while (read()) solve();
  return 0;
}
