#include <bits/stdc++.h>
using namespace std;
struct matrix {
  long long m[2][2];
  inline matrix() {}
  inline matrix(int a) { m[0][0] = m[0][1] = m[1][0] = m[1][1] = a; }
  inline matrix(int a, int b, int c, int d) {
    m[0][0] = a;
    m[0][1] = b;
    m[1][0] = c;
    m[1][1] = d;
  }
};
inline matrix Plus(matrix a, matrix b) {
  return matrix((a.m[0][0] + b.m[0][0]) % 1000000000,
                (a.m[0][1] + b.m[0][1]) % 1000000000,
                (a.m[1][0] + b.m[1][0]) % 1000000000,
                (a.m[1][1] + b.m[1][1]) % 1000000000);
}
inline void Plusto(matrix& a, matrix b) {
  a.m[0][0] = (a.m[0][0] + b.m[0][0]) % 1000000000;
  a.m[0][1] = (a.m[0][1] + b.m[0][1]) % 1000000000;
  a.m[1][0] = (a.m[1][0] + b.m[1][0]) % 1000000000;
  a.m[1][1] = (a.m[1][1] + b.m[1][1]) % 1000000000;
}
inline matrix times(matrix a, matrix b) {
  return matrix((a.m[0][0] * b.m[0][0] % 1000000000 +
                 a.m[0][1] * b.m[1][0] % 1000000000) %
                    1000000000,
                (a.m[0][0] * b.m[0][1] % 1000000000 +
                 a.m[0][1] * b.m[1][1] % 1000000000) %
                    1000000000,
                (a.m[1][0] * b.m[0][0] % 1000000000 +
                 a.m[1][1] * b.m[1][0] % 1000000000) %
                    1000000000,
                (a.m[1][0] * b.m[0][1] % 1000000000 +
                 a.m[1][1] * b.m[1][1] % 1000000000) %
                    1000000000);
}
inline void timesto(matrix& a, matrix b) {
  tie(a.m[0][0], a.m[0][1]) = make_pair((a.m[0][0] * b.m[0][0] % 1000000000 +
                                         a.m[0][1] * b.m[1][0] % 1000000000) %
                                            1000000000,
                                        (a.m[0][0] * b.m[0][1] % 1000000000 +
                                         a.m[0][1] * b.m[1][1] % 1000000000) %
                                            1000000000);
  tie(a.m[1][0], a.m[1][1]) = make_pair((a.m[1][0] * b.m[0][0] % 1000000000 +
                                         a.m[1][1] * b.m[1][0] % 1000000000) %
                                            1000000000,
                                        (a.m[1][0] * b.m[0][1] % 1000000000 +
                                         a.m[1][1] * b.m[1][1] % 1000000000) %
                                            1000000000);
}
matrix fibs[200007] = {matrix(1, 0, 0, 1), matrix(1, 1, 1, 0)},
       fibq[200007] = {matrix(0), matrix(1, 0, 0, 1)};
matrix dt[2000007], ic[2000007];
int n, k;
inline void LiSimon() {
  for (int i = 2; i < 200007; i++) fibs[i] = times(fibs[i - 1], fibs[1]);
  for (int i = 2; i < 200007; i++) fibq[i] = Plus(fibq[i - 1], fibs[i - 1]);
}
inline void YangAnnie(int now, int nl, int nr, int djg, int what) {
  int m = (nl + nr) / 2;
  if (ic[now].m[0][0]) {
    Plusto(dt[now * 2], times(fibq[m - nl + 1], ic[now]));
    Plusto(dt[now * 2 + 1], times(fibq[nr - m], ic[now]));
    Plusto(ic[now * 2], ic[now]);
    Plusto(ic[now * 2 + 1], ic[now]);
    ic[now] = matrix(0);
  }
  if (nl == djg && nr == djg) {
    dt[now].m[0][0] = what;
    dt[now].m[1][0] = what;
    return;
  }
  if (m >= djg)
    YangAnnie(now * 2, nl, m, djg, what);
  else
    YangAnnie(now * 2 + 1, m + 1, nr, djg, what);
  dt[now] = Plus(times(fibs[m - nl + 1], dt[now * 2 + 1]), dt[now * 2]);
}
inline matrix YanZack(int now, int nl, int nr, int l, int r) {
  if (nl > r || nr < l) return matrix(0);
  int m = (nl + nr) / 2;
  if (ic[now].m[0][0]) {
    Plusto(dt[now * 2], times(fibq[m - nl + 1], ic[now]));
    Plusto(dt[now * 2 + 1], times(fibq[nr - m], ic[now]));
    Plusto(ic[now * 2], ic[now]);
    Plusto(ic[now * 2 + 1], ic[now]);
    ic[now] = matrix(0);
  }
  if (nl >= l && nr <= r) {
    return times(fibs[nl - l], dt[now]);
  }
  return Plus(YanZack(now * 2, nl, m, l, r),
              YanZack(now * 2 + 1, m + 1, nr, l, r));
}
inline void SunSandy(int now, int nl, int nr, int l, int r, int what) {
  if (nl > r || nr < l) return;
  int m = (nl + nr) / 2;
  if (ic[now].m[0][0]) {
    Plusto(dt[now * 2], times(fibq[m - nl + 1], ic[now]));
    Plusto(dt[now * 2 + 1], times(fibq[nr - m], ic[now]));
    Plusto(ic[now * 2], ic[now]);
    Plusto(ic[now * 2 + 1], ic[now]);
    ic[now] = matrix(0);
  }
  if (nl >= l && nr <= r) {
    ic[now].m[0][0] += what;
    ic[now].m[1][0] += what;
    Plusto(dt[now], times(fibq[nr - nl + 1], ic[now]));
    return;
  }
  SunSandy(now * 2, nl, m, l, r, what);
  SunSandy(now * 2 + 1, m + 1, nr, l, r, what);
  dt[now] = Plus(times(fibs[m - nl + 1], dt[now * 2 + 1]), dt[now * 2]);
}
inline void LiAmy() {
  int a, b;
  scanf("%d%d", &a, &b);
  a--, b--;
  printf("%I64d\n", YanZack(1, 0, n - 1, a, b).m[1][0]);
}
inline void SunTom() {
  int a, b, c;
  scanf("%d%d%d", &a, &b, &c);
  a--, b--;
  SunSandy(1, 0, n - 1, a, b, c);
}
inline void ZhuMary() {
  int a, b;
  scanf("%d%d", &a, &b);
  a--;
  YangAnnie(1, 0, n - 1, a, b);
}
inline void XuanAlex() {
  scanf("%d%d", &n, &k);
  for (int i = 0; i < n; i++) {
    int a;
    scanf("%d", &a);
    YangAnnie(1, 0, n - 1, i, a);
  }
  for (int i = 0; i < k; i++) {
    int mode;
    scanf("%d", &mode);
    if (mode == 1)
      ZhuMary();
    else if (mode == 2)
      LiAmy();
    else
      SunTom();
  }
}
int main() {
  LiSimon();
  XuanAlex();
  return 0;
}

### Prompt

Please create a solution in CPP to 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>
using namespace std;
struct matrix {
  long long m[2][2];
  inline matrix() {}
  inline matrix(int a) { m[0][0] = m[0][1] = m[1][0] = m[1][1] = a; }
  inline matrix(int a, int b, int c, int d) {
    m[0][0] = a;
    m[0][1] = b;
    m[1][0] = c;
    m[1][1] = d;
  }
};
inline matrix Plus(matrix a, matrix b) {
  return matrix((a.m[0][0] + b.m[0][0]) % 1000000000,
                (a.m[0][1] + b.m[0][1]) % 1000000000,
                (a.m[1][0] + b.m[1][0]) % 1000000000,
                (a.m[1][1] + b.m[1][1]) % 1000000000);
}
inline void Plusto(matrix& a, matrix b) {
  a.m[0][0] = (a.m[0][0] + b.m[0][0]) % 1000000000;
  a.m[0][1] = (a.m[0][1] + b.m[0][1]) % 1000000000;
  a.m[1][0] = (a.m[1][0] + b.m[1][0]) % 1000000000;
  a.m[1][1] = (a.m[1][1] + b.m[1][1]) % 1000000000;
}
inline matrix times(matrix a, matrix b) {
  return matrix((a.m[0][0] * b.m[0][0] % 1000000000 +
                 a.m[0][1] * b.m[1][0] % 1000000000) %
                    1000000000,
                (a.m[0][0] * b.m[0][1] % 1000000000 +
                 a.m[0][1] * b.m[1][1] % 1000000000) %
                    1000000000,
                (a.m[1][0] * b.m[0][0] % 1000000000 +
                 a.m[1][1] * b.m[1][0] % 1000000000) %
                    1000000000,
                (a.m[1][0] * b.m[0][1] % 1000000000 +
                 a.m[1][1] * b.m[1][1] % 1000000000) %
                    1000000000);
}
inline void timesto(matrix& a, matrix b) {
  tie(a.m[0][0], a.m[0][1]) = make_pair((a.m[0][0] * b.m[0][0] % 1000000000 +
                                         a.m[0][1] * b.m[1][0] % 1000000000) %
                                            1000000000,
                                        (a.m[0][0] * b.m[0][1] % 1000000000 +
                                         a.m[0][1] * b.m[1][1] % 1000000000) %
                                            1000000000);
  tie(a.m[1][0], a.m[1][1]) = make_pair((a.m[1][0] * b.m[0][0] % 1000000000 +
                                         a.m[1][1] * b.m[1][0] % 1000000000) %
                                            1000000000,
                                        (a.m[1][0] * b.m[0][1] % 1000000000 +
                                         a.m[1][1] * b.m[1][1] % 1000000000) %
                                            1000000000);
}
matrix fibs[200007] = {matrix(1, 0, 0, 1), matrix(1, 1, 1, 0)},
       fibq[200007] = {matrix(0), matrix(1, 0, 0, 1)};
matrix dt[2000007], ic[2000007];
int n, k;
inline void LiSimon() {
  for (int i = 2; i < 200007; i++) fibs[i] = times(fibs[i - 1], fibs[1]);
  for (int i = 2; i < 200007; i++) fibq[i] = Plus(fibq[i - 1], fibs[i - 1]);
}
inline void YangAnnie(int now, int nl, int nr, int djg, int what) {
  int m = (nl + nr) / 2;
  if (ic[now].m[0][0]) {
    Plusto(dt[now * 2], times(fibq[m - nl + 1], ic[now]));
    Plusto(dt[now * 2 + 1], times(fibq[nr - m], ic[now]));
    Plusto(ic[now * 2], ic[now]);
    Plusto(ic[now * 2 + 1], ic[now]);
    ic[now] = matrix(0);
  }
  if (nl == djg && nr == djg) {
    dt[now].m[0][0] = what;
    dt[now].m[1][0] = what;
    return;
  }
  if (m >= djg)
    YangAnnie(now * 2, nl, m, djg, what);
  else
    YangAnnie(now * 2 + 1, m + 1, nr, djg, what);
  dt[now] = Plus(times(fibs[m - nl + 1], dt[now * 2 + 1]), dt[now * 2]);
}
inline matrix YanZack(int now, int nl, int nr, int l, int r) {
  if (nl > r || nr < l) return matrix(0);
  int m = (nl + nr) / 2;
  if (ic[now].m[0][0]) {
    Plusto(dt[now * 2], times(fibq[m - nl + 1], ic[now]));
    Plusto(dt[now * 2 + 1], times(fibq[nr - m], ic[now]));
    Plusto(ic[now * 2], ic[now]);
    Plusto(ic[now * 2 + 1], ic[now]);
    ic[now] = matrix(0);
  }
  if (nl >= l && nr <= r) {
    return times(fibs[nl - l], dt[now]);
  }
  return Plus(YanZack(now * 2, nl, m, l, r),
              YanZack(now * 2 + 1, m + 1, nr, l, r));
}
inline void SunSandy(int now, int nl, int nr, int l, int r, int what) {
  if (nl > r || nr < l) return;
  int m = (nl + nr) / 2;
  if (ic[now].m[0][0]) {
    Plusto(dt[now * 2], times(fibq[m - nl + 1], ic[now]));
    Plusto(dt[now * 2 + 1], times(fibq[nr - m], ic[now]));
    Plusto(ic[now * 2], ic[now]);
    Plusto(ic[now * 2 + 1], ic[now]);
    ic[now] = matrix(0);
  }
  if (nl >= l && nr <= r) {
    ic[now].m[0][0] += what;
    ic[now].m[1][0] += what;
    Plusto(dt[now], times(fibq[nr - nl + 1], ic[now]));
    return;
  }
  SunSandy(now * 2, nl, m, l, r, what);
  SunSandy(now * 2 + 1, m + 1, nr, l, r, what);
  dt[now] = Plus(times(fibs[m - nl + 1], dt[now * 2 + 1]), dt[now * 2]);
}
inline void LiAmy() {
  int a, b;
  scanf("%d%d", &a, &b);
  a--, b--;
  printf("%I64d\n", YanZack(1, 0, n - 1, a, b).m[1][0]);
}
inline void SunTom() {
  int a, b, c;
  scanf("%d%d%d", &a, &b, &c);
  a--, b--;
  SunSandy(1, 0, n - 1, a, b, c);
}
inline void ZhuMary() {
  int a, b;
  scanf("%d%d", &a, &b);
  a--;
  YangAnnie(1, 0, n - 1, a, b);
}
inline void XuanAlex() {
  scanf("%d%d", &n, &k);
  for (int i = 0; i < n; i++) {
    int a;
    scanf("%d", &a);
    YangAnnie(1, 0, n - 1, i, a);
  }
  for (int i = 0; i < k; i++) {
    int mode;
    scanf("%d", &mode);
    if (mode == 1)
      ZhuMary();
    else if (mode == 2)
      LiAmy();
    else
      SunTom();
  }
}
int main() {
  LiSimon();
  XuanAlex();
  return 0;
}

```