#include <bits/stdc++.h>
using namespace std;
int mod = 1e9;
int n, m;
long long f[1000000];
struct node {
  int l, r;
  long long s[2];
} a[1000000];
long long in[300000];
long long getFib(long long a, long long b, int idx) {
  if (idx == 0)
    return a;
  else if (idx == 1)
    return b;
  else {
    return (f[idx - 2] * a + f[idx - 1] * b) % mod;
  }
}
void maketree(int l, int r, int rt) {
  a[rt].l = l;
  a[rt].r = r;
  a[rt].s[0] = 0;
  for (int i = 0; i <= r - l; i++) {
    a[rt].s[0] += f[i] * in[i + l];
    a[rt].s[0] %= mod;
  }
  a[rt].s[1] = 0;
  for (int i = 0; i <= r - l; i++) {
    a[rt].s[1] += f[i + 1] * in[i + l];
    a[rt].s[1] %= mod;
  }
  if (l == r) return;
  int mid = (l + r) / 2;
  maketree(l, mid, rt * 2);
  maketree(mid + 1, r, rt * 2 + 1);
}
void modify(int l, long long v, int rt) {
  a[rt].s[0] += f[l - a[rt].l] * (v - in[l]);
  a[rt].s[0] = (a[rt].s[0] % mod + mod) % mod;
  a[rt].s[1] += f[l - a[rt].l + 1] * (v - in[l]);
  a[rt].s[1] = (a[rt].s[1] % mod + mod) % mod;
  if (a[rt].l == a[rt].r) {
    in[l] = v;
    return;
  }
  int mid = (a[rt].l + a[rt].r) / 2;
  if (l <= mid)
    modify(l, v, rt * 2);
  else
    modify(l, v, rt * 2 + 1);
}
void query(int l, int r, int rt, long long& s0, long long& s1) {
  if (l == a[rt].l && r == a[rt].r) {
    s0 = a[rt].s[0];
    s1 = a[rt].s[1];
    return;
  }
  int mid = (a[rt].l + a[rt].r) / 2;
  if (r <= mid) {
    long long t0, t1;
    query(l, r, rt * 2, t0, t1);
    s0 = t0;
    s1 = t1;
  } else if (l > mid) {
    long long t0, t1;
    query(l, r, rt * 2 + 1, t0, t1);
    s0 = t0;
    s1 = t1;
  } else {
    long long t00, t01, t10, t11;
    query(l, mid, rt * 2, t00, t01);
    query(mid + 1, r, rt * 2 + 1, t10, t11);
    s0 = t00 + getFib(t10, t11, mid - l + 1);
    s1 = t01 + getFib(t10, t11, mid - l + 2);
    s0 %= mod;
    s1 %= mod;
  }
}
int main() {
  f[0] = f[1] = 1;
  for (int i = 2; i < 1000000; i++) {
    f[i] = f[i - 1] + f[i - 2];
    f[i] %= mod;
  }
  cin >> n >> m;
  for (int i = 1; i <= n; i++) cin >> in[i];
  maketree(1, n, 1);
  while (m--) {
    int type;
    cin >> type;
    if (type == 1) {
      int x;
      long long v;
      cin >> x >> v;
      modify(x, v, 1);
    } else {
      int l, r;
      long long s0, s1;
      cin >> l >> r;
      query(l, r, 1, s0, s1);
      cout << s0 << '\n';
    }
  }
  return 0;
}

### Prompt

Develop a solution in CPP 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;
int mod = 1e9;
int n, m;
long long f[1000000];
struct node {
  int l, r;
  long long s[2];
} a[1000000];
long long in[300000];
long long getFib(long long a, long long b, int idx) {
  if (idx == 0)
    return a;
  else if (idx == 1)
    return b;
  else {
    return (f[idx - 2] * a + f[idx - 1] * b) % mod;
  }
}
void maketree(int l, int r, int rt) {
  a[rt].l = l;
  a[rt].r = r;
  a[rt].s[0] = 0;
  for (int i = 0; i <= r - l; i++) {
    a[rt].s[0] += f[i] * in[i + l];
    a[rt].s[0] %= mod;
  }
  a[rt].s[1] = 0;
  for (int i = 0; i <= r - l; i++) {
    a[rt].s[1] += f[i + 1] * in[i + l];
    a[rt].s[1] %= mod;
  }
  if (l == r) return;
  int mid = (l + r) / 2;
  maketree(l, mid, rt * 2);
  maketree(mid + 1, r, rt * 2 + 1);
}
void modify(int l, long long v, int rt) {
  a[rt].s[0] += f[l - a[rt].l] * (v - in[l]);
  a[rt].s[0] = (a[rt].s[0] % mod + mod) % mod;
  a[rt].s[1] += f[l - a[rt].l + 1] * (v - in[l]);
  a[rt].s[1] = (a[rt].s[1] % mod + mod) % mod;
  if (a[rt].l == a[rt].r) {
    in[l] = v;
    return;
  }
  int mid = (a[rt].l + a[rt].r) / 2;
  if (l <= mid)
    modify(l, v, rt * 2);
  else
    modify(l, v, rt * 2 + 1);
}
void query(int l, int r, int rt, long long& s0, long long& s1) {
  if (l == a[rt].l && r == a[rt].r) {
    s0 = a[rt].s[0];
    s1 = a[rt].s[1];
    return;
  }
  int mid = (a[rt].l + a[rt].r) / 2;
  if (r <= mid) {
    long long t0, t1;
    query(l, r, rt * 2, t0, t1);
    s0 = t0;
    s1 = t1;
  } else if (l > mid) {
    long long t0, t1;
    query(l, r, rt * 2 + 1, t0, t1);
    s0 = t0;
    s1 = t1;
  } else {
    long long t00, t01, t10, t11;
    query(l, mid, rt * 2, t00, t01);
    query(mid + 1, r, rt * 2 + 1, t10, t11);
    s0 = t00 + getFib(t10, t11, mid - l + 1);
    s1 = t01 + getFib(t10, t11, mid - l + 2);
    s0 %= mod;
    s1 %= mod;
  }
}
int main() {
  f[0] = f[1] = 1;
  for (int i = 2; i < 1000000; i++) {
    f[i] = f[i - 1] + f[i - 2];
    f[i] %= mod;
  }
  cin >> n >> m;
  for (int i = 1; i <= n; i++) cin >> in[i];
  maketree(1, n, 1);
  while (m--) {
    int type;
    cin >> type;
    if (type == 1) {
      int x;
      long long v;
      cin >> x >> v;
      modify(x, v, 1);
    } else {
      int l, r;
      long long s0, s1;
      cin >> l >> r;
      query(l, r, 1, s0, s1);
      cout << s0 << '\n';
    }
  }
  return 0;
}

```