#include <bits/stdc++.h>
using namespace std;
const int inf = 1e9;
const double eps = 1e-9;
const double INF = inf;
const double EPS = eps;
int A[(1 << 19) + 100][2], F[(1 << 19) + 100], Len[(1 << 19) + 100];
void merge(int v) {
  assert(Len[v] >= 2);
  A[v][0] = (A[2 * v][0] + A[2 * v + 1][0] * 1ll * F[Len[v] / 2 + 1] +
             A[2 * v + 1][1] * 1ll * F[Len[v] / 2]) %
            inf;
  A[v][1] = (A[2 * v][1] + A[2 * v + 1][0] * 1ll * F[Len[v] / 2] +
             A[2 * v + 1][1] * 1ll * F[Len[v] / 2 - 1]) %
            inf;
}
void st(int v, int l, int r, int p, int d) {
  if (r - l == 1) {
    A[v][0] = d, A[v][1] = 0;
    return;
  }
  (p < (l + r) / 2) ? (st(2 * v, l, (l + r) / 2, p, d))
                    : (st(2 * v + 1, (l + r) / 2, r, p, d));
  merge(v);
}
void sum(int v, int l, int r, int L, int R, pair<int, int>& ret) {
  if (L <= l && r <= R) {
    ret = make_pair(A[v][0], A[v][1]);
    return;
  }
  if (R <= l || r <= L) {
    ret = make_pair(0, 0);
    return;
  }
  pair<int, int> ret2;
  sum(2 * v, l, (l + r) / 2, L, R, ret);
  sum(2 * v + 1, (l + r) / 2, r, L, R, ret2);
  int len = (l + r) / 2 - max(l, L);
  if (len <= 0) {
    ret = ret2;
    return;
  }
  ret.first =
      (ret.first + ret2.first * 1ll * F[len + 1] + ret2.second * 1ll * F[len]) %
      inf;
  ret.second = (ret.second + ret2.first * 1ll * F[len] +
                ret2.second * 1ll * F[len - 1]) %
               inf;
}
int main() {
  int i, l, r, tmp, tp, n, m, p;
  scanf("%d%d", &n, &m);
  for (F[0] = 0, F[1] = 1, i = 2; i < (1 << 19) + 100; i++)
    F[i] = (F[i - 1] + F[i - 2]) % inf;
  for (i = (1 << 19) - 1; i >= (1 << 18); i--) Len[i] = 1;
  for (i = (1 << 18) - 1; i > 0; i--) Len[i] = 2 * Len[2 * i];
  for (i = 0; i < n; i++) scanf("%d", &tmp), st(1, 0, (1 << 18), i, tmp);
  for (i = 0; i < m; i++) {
    scanf("%d", &tp);
    if (tp == 1) {
      scanf("%d%d", &p, &tmp), st(1, 0, (1 << 18), p - 1, tmp);
      continue;
    }
    if (tp == 2) {
      scanf("%d%d", &l, &r), l--;
      pair<int, int> res;
      sum(1, 0, (1 << 18), l, r, res);
      printf("%d\n", (res.first) % inf);
      continue;
    }
  };
  return 0;
}

### Prompt

Please provide a Cpp coded solution to the problem described below:

By the age of three Smart Beaver mastered all arithmetic operations and got this summer homework from the amazed teacher:

You are given a sequence of integers a1, a2, ..., an. Your task is to perform on it m consecutive operations of the following type:

  1. For given numbers xi and vi assign value vi to element axi. 
  2. For given numbers li and ri you've got to calculate sum <image>, where f0 = f1 = 1 and at i ≥ 2: fi = fi - 1 + fi - 2. 
  3. For a group of three numbers li ri di you should increase value ax by di for all x (li ≤ x ≤ ri). 



Smart Beaver planned a tour around great Canadian lakes, so he asked you to help him solve the given problem.

Input

The first line contains two integers n and m (1 ≤ n, m ≤ 2·105) — the number of integers in the sequence and the number of operations, correspondingly. The second line contains n integers a1, a2, ..., an (0 ≤ ai ≤ 105). Then follow m lines, each describes an operation. Each line starts with an integer ti (1 ≤ ti ≤ 3) — the operation type: 

  * if ti = 1, then next follow two integers xi vi (1 ≤ xi ≤ n, 0 ≤ vi ≤ 105); 
  * if ti = 2, then next follow two integers li ri (1 ≤ li ≤ ri ≤ n); 
  * if ti = 3, then next follow three integers li ri di (1 ≤ li ≤ ri ≤ n, 0 ≤ di ≤ 105). 



The input limits for scoring 30 points are (subproblem E1): 

  * It is guaranteed that n does not exceed 100, m does not exceed 10000 and there will be no queries of the 3-rd type. 



The input limits for scoring 70 points are (subproblems E1+E2): 

  * It is guaranteed that there will be queries of the 1-st and 2-nd type only. 



The input limits for scoring 100 points are (subproblems E1+E2+E3): 

  * No extra limitations. 

Output

For each query print the calculated sum modulo 1000000000 (109).

Examples

Input

5 5
1 3 1 2 4
2 1 4
2 1 5
2 2 4
1 3 10
2 1 5


Output

12
32
8
50


Input

5 4
1 3 1 2 4
3 1 4 1
2 2 4
1 2 10
2 1 5


Output

12
45

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
const int inf = 1e9;
const double eps = 1e-9;
const double INF = inf;
const double EPS = eps;
int A[(1 << 19) + 100][2], F[(1 << 19) + 100], Len[(1 << 19) + 100];
void merge(int v) {
  assert(Len[v] >= 2);
  A[v][0] = (A[2 * v][0] + A[2 * v + 1][0] * 1ll * F[Len[v] / 2 + 1] +
             A[2 * v + 1][1] * 1ll * F[Len[v] / 2]) %
            inf;
  A[v][1] = (A[2 * v][1] + A[2 * v + 1][0] * 1ll * F[Len[v] / 2] +
             A[2 * v + 1][1] * 1ll * F[Len[v] / 2 - 1]) %
            inf;
}
void st(int v, int l, int r, int p, int d) {
  if (r - l == 1) {
    A[v][0] = d, A[v][1] = 0;
    return;
  }
  (p < (l + r) / 2) ? (st(2 * v, l, (l + r) / 2, p, d))
                    : (st(2 * v + 1, (l + r) / 2, r, p, d));
  merge(v);
}
void sum(int v, int l, int r, int L, int R, pair<int, int>& ret) {
  if (L <= l && r <= R) {
    ret = make_pair(A[v][0], A[v][1]);
    return;
  }
  if (R <= l || r <= L) {
    ret = make_pair(0, 0);
    return;
  }
  pair<int, int> ret2;
  sum(2 * v, l, (l + r) / 2, L, R, ret);
  sum(2 * v + 1, (l + r) / 2, r, L, R, ret2);
  int len = (l + r) / 2 - max(l, L);
  if (len <= 0) {
    ret = ret2;
    return;
  }
  ret.first =
      (ret.first + ret2.first * 1ll * F[len + 1] + ret2.second * 1ll * F[len]) %
      inf;
  ret.second = (ret.second + ret2.first * 1ll * F[len] +
                ret2.second * 1ll * F[len - 1]) %
               inf;
}
int main() {
  int i, l, r, tmp, tp, n, m, p;
  scanf("%d%d", &n, &m);
  for (F[0] = 0, F[1] = 1, i = 2; i < (1 << 19) + 100; i++)
    F[i] = (F[i - 1] + F[i - 2]) % inf;
  for (i = (1 << 19) - 1; i >= (1 << 18); i--) Len[i] = 1;
  for (i = (1 << 18) - 1; i > 0; i--) Len[i] = 2 * Len[2 * i];
  for (i = 0; i < n; i++) scanf("%d", &tmp), st(1, 0, (1 << 18), i, tmp);
  for (i = 0; i < m; i++) {
    scanf("%d", &tp);
    if (tp == 1) {
      scanf("%d%d", &p, &tmp), st(1, 0, (1 << 18), p - 1, tmp);
      continue;
    }
    if (tp == 2) {
      scanf("%d%d", &l, &r), l--;
      pair<int, int> res;
      sum(1, 0, (1 << 18), l, r, res);
      printf("%d\n", (res.first) % inf);
      continue;
    }
  };
  return 0;
}

```