#include <bits/stdc++.h>
long long fib[200111];
long long the[2][(1 << 20)], t[(1 << 20)];
int T;
int n, q, i, j, k;
long long query(int l, int r, int id, int b) {
  if (l == 1 && r == t[id]) return the[1][id];
  if (l || r != t[id]) {
    if (r <= t[(id << 1)]) return query(l, r, (id << 1), b);
    if (l >= t[(id << 1)])
      return query(l - t[(id << 1)], r - t[(id << 1)], (id << 1 ^ 1), b);
    return (query(l, t[(id << 1)], (id << 1), b) +
            query(0, r - t[(id << 1)], (id << 1 ^ 1), b + t[(id << 1)] - l)) %
           1000000000ll;
  }
  return (the[0][id] * fib[b] + the[1][id] * (b ? fib[b - 1] : 0)) %
         1000000000ll;
}
int main() {
  fib[0] = fib[1] = 1ll;
  for (i = 2; i < 200111; ++i)
    fib[i] = (fib[i - 1] + fib[i - 2]) % 1000000000ll;
  scanf("%d %d", &n, &q);
  for (T = 1; T < n; T <<= 1)
    ;
  for (i = 0; i < n; ++i) scanf("%I64d", the[0] + i + T);
  for (i = 0; i < T; ++i) t[i + T] = 1;
  for (i = T - 1; i >= 0; --i) {
    t[i] = t[i << 1] << 1;
    the[0][i] = (query(0, t[i << 1], i << 1, 0) +
                 query(0, t[i << 1], i << 1 ^ 1, t[i << 1])) %
                1000000000ll;
    the[1][i] = (query(1, t[i << 1], i << 1, 0) +
                 query(0, t[i << 1], i << 1 ^ 1, t[i << 1] - 1)) %
                1000000000ll;
  }
  while (q--) {
    scanf("%d", &i);
    if (i == 1) {
      scanf("%d %d", &i, &j);
      i += T - 1;
      the[0][i] = j;
      while (i >>= 1) {
        the[0][i] = (query(0, t[i << 1], i << 1, 0) +
                     query(0, t[i << 1], i << 1 ^ 1, t[i << 1])) %
                    1000000000ll;
        the[1][i] = (query(1, t[i << 1], i << 1, 0) +
                     query(0, t[i << 1], i << 1 ^ 1, t[i << 1] - 1)) %
                    1000000000ll;
      }
    } else {
      scanf("%d %d", &i, &j);
      printf("%I64d\n", query(--i, j, 1, 0));
    }
  }
  return 0;
}

### Prompt

In Cpp, your task is to solve the following problem:

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>
long long fib[200111];
long long the[2][(1 << 20)], t[(1 << 20)];
int T;
int n, q, i, j, k;
long long query(int l, int r, int id, int b) {
  if (l == 1 && r == t[id]) return the[1][id];
  if (l || r != t[id]) {
    if (r <= t[(id << 1)]) return query(l, r, (id << 1), b);
    if (l >= t[(id << 1)])
      return query(l - t[(id << 1)], r - t[(id << 1)], (id << 1 ^ 1), b);
    return (query(l, t[(id << 1)], (id << 1), b) +
            query(0, r - t[(id << 1)], (id << 1 ^ 1), b + t[(id << 1)] - l)) %
           1000000000ll;
  }
  return (the[0][id] * fib[b] + the[1][id] * (b ? fib[b - 1] : 0)) %
         1000000000ll;
}
int main() {
  fib[0] = fib[1] = 1ll;
  for (i = 2; i < 200111; ++i)
    fib[i] = (fib[i - 1] + fib[i - 2]) % 1000000000ll;
  scanf("%d %d", &n, &q);
  for (T = 1; T < n; T <<= 1)
    ;
  for (i = 0; i < n; ++i) scanf("%I64d", the[0] + i + T);
  for (i = 0; i < T; ++i) t[i + T] = 1;
  for (i = T - 1; i >= 0; --i) {
    t[i] = t[i << 1] << 1;
    the[0][i] = (query(0, t[i << 1], i << 1, 0) +
                 query(0, t[i << 1], i << 1 ^ 1, t[i << 1])) %
                1000000000ll;
    the[1][i] = (query(1, t[i << 1], i << 1, 0) +
                 query(0, t[i << 1], i << 1 ^ 1, t[i << 1] - 1)) %
                1000000000ll;
  }
  while (q--) {
    scanf("%d", &i);
    if (i == 1) {
      scanf("%d %d", &i, &j);
      i += T - 1;
      the[0][i] = j;
      while (i >>= 1) {
        the[0][i] = (query(0, t[i << 1], i << 1, 0) +
                     query(0, t[i << 1], i << 1 ^ 1, t[i << 1])) %
                    1000000000ll;
        the[1][i] = (query(1, t[i << 1], i << 1, 0) +
                     query(0, t[i << 1], i << 1 ^ 1, t[i << 1] - 1)) %
                    1000000000ll;
      }
    } else {
      scanf("%d %d", &i, &j);
      printf("%I64d\n", query(--i, j, 1, 0));
    }
  }
  return 0;
}

```