#include <bits/stdc++.h>
using namespace std;
struct Matrix {
  long long A, B, C, D;
};
struct AnsType {
  int Len;
  long long A, B;
};
int Get() {
  char c;
  while (c = getchar(), (c < '0' || c > '9') && (c != '-'))
    ;
  bool Flag = (c == '-');
  if (Flag) c = getchar();
  int X = 0;
  while (c >= '0' && c <= '9') {
    X = X * 10 + c - 48;
    c = getchar();
  }
  return Flag ? -X : X;
}
void Output(int X) {
  if (X < 0) {
    putchar('-');
    X = -X;
  }
  int Len = 0, Data[10];
  while (X) {
    Data[Len++] = X % 10;
    X /= 10;
  }
  if (!Len) Data[Len++] = 0;
  while (Len--) putchar(Data[Len] + 48);
  putchar('\n');
}
const int Mod = 1000000000;
long long Data[200000];
int Left[524288], Right[524288];
AnsType Sum[524288];
Matrix F[200001];
Matrix operator*(Matrix X, Matrix Y) {
  Matrix Ans;
  Ans.A = (X.A * Y.A + X.B * Y.C) % Mod;
  Ans.B = (X.A * Y.B + X.B * Y.D) % Mod;
  Ans.C = (X.C * Y.A + X.D * Y.C) % Mod;
  Ans.D = (X.C * Y.B + X.D * Y.D) % Mod;
  return Ans;
}
AnsType operator+(AnsType L, AnsType R) {
  AnsType Ans;
  Ans.Len = L.Len + R.Len;
  Ans.A = (L.A + R.A * F[L.Len].A + R.B * F[L.Len].C) % Mod;
  Ans.B = (L.B + R.A * F[L.Len].B + R.B * F[L.Len].D) % Mod;
  return Ans;
}
void Build(int P, int L, int R) {
  Left[P] = L;
  Right[P] = R;
  if (L == R) {
    Sum[P].Len = 1;
    Sum[P].A = Sum[P].B = Data[L];
  } else {
    int Mid = (L + R) / 2;
    Build(P * 2, L, Mid);
    Build(P * 2 + 1, Mid + 1, R);
    Sum[P] = Sum[P * 2] + Sum[P * 2 + 1];
  }
}
void Update(int P, int X, int Y) {
  if (Left[P] == Right[P]) {
    Sum[P].A = Sum[P].B = Y;
    return;
  }
  int Mid = (Left[P] + Right[P]) / 2;
  if (X <= Mid)
    Update(P * 2, X, Y);
  else
    Update(P * 2 + 1, X, Y);
  Sum[P] = Sum[P * 2] + Sum[P * 2 + 1];
}
AnsType Query(int P, int L, int R) {
  if (Left[P] == L && Right[P] == R) return Sum[P];
  int Mid = (Left[P] + Right[P]) / 2;
  if (R <= Mid) return Query(P * 2, L, R);
  if (L > Mid) return Query(P * 2 + 1, L, R);
  return Query(P * 2, L, Mid) + Query(P * 2 + 1, Mid + 1, R);
}
int main() {
  int N = Get(), M = Get();
  F[0] = (Matrix){1, 0, 0, 1};
  for (int i = 1; i <= N; i++) F[i] = F[i - 1] * (Matrix){0, 1, 1, 1};
  for (int i = 0; i < N; i++) Data[i] = Get();
  Build(1, 0, N - 1);
  while (M--) {
    int Type = Get(), X = Get(), Y = Get();
    if (Type == 1)
      Update(1, X - 1, Y);
    else
      Output(Query(1, X - 1, Y - 1).A);
  }
  return 0;
}
