#include <bits/stdc++.h>
using namespace std;
int MAX = 1000000;
int MIN = -1000000;
int INF = 1000000000;
int x4[4] = {0, 1, 0, -1};
int y4[4] = {1, 0, -1, 0};
int x8[8] = {0, 1, 1, 1, 0, -1, -1, -1};
int y8[8] = {1, 1, 0, -1, -1, -1, 0, 1};
int i, j, k;
long long mod = 1000000000ll;
int main() {
  long long n, m, arr[2000];
  long long fib[2000], t, A, B;
  fib[0] = 1ll;
  fib[1] = 1ll;
  for (i = 2; i <= 1500; i++) fib[i] = (fib[i - 1] + fib[i - 2]) % mod;
  cin >> n >> m;
  for (i = (0); i < (n); i++) cin >> arr[i];
  for (i = (0); i < (m); i++) {
    cin >> t >> A >> B;
    if (t == 1) arr[--A] = B;
    if (t == 2) {
      A--, B--;
      long long sum = 0ll;
      for (j = 0; j <= (B - A); j++) sum = (sum + (fib[j] * arr[A + j])) % mod;
      cout << sum << endl;
    }
  }
  {
    fflush(stdin);
    getchar();
  };
  return 0;
}
