#include <bits/stdc++.h>
using namespace std;
const int maxn = 200005;
const int mod = 1e9;
long long f[maxn];
int n;
int pos;
struct segtree {
  long long sum[maxn << 2][2], add[maxn << 2];
  inline void pushUp(int l, int r, int rt) {
    int m = (l + r) >> 1;
    sum[rt][0] = (sum[rt << 1][0] + shift(m - l + 1, rt << 1 | 1)) % mod;
    sum[rt][1] = (sum[rt << 1][1] + shift(m - l + 2, rt << 1 | 1)) % mod;
  }
  inline void Down(int len, int rt, int kd) {
    long long tp;
    if (kd == 1) {
      tp = (f[len + 2] - 2 + mod) % mod;
    } else
      tp = (f[len + 1] - 1 + mod) % mod;
    tp = tp * add[rt] % mod * len % mod;
    sum[rt][kd] += tp;
    sum[rt][kd] %= mod;
  }
  inline void up(int len, int rt, int kd, int v) {
    long long tp;
    if (kd == 1) {
      tp = (f[len + 2] - 2 + mod) % mod;
    } else
      tp = (f[len + 1] - 1 + mod) % mod;
    tp = tp * v % mod * len % mod;
    sum[rt][kd] += tp;
    sum[rt][kd] %= mod;
  }
  void update(int L, int R, int v, int l = 1, int r = n, int rt = 1) {
    if (L <= l && r <= R) {
      add[rt] = (add[rt] + v) % mod;
      up(r - l + 1, rt, 0, v);
      up(r - l + 1, rt, 1, v);
      return;
    }
    int m = (l + r) >> 1;
    pushDown(l, r, rt);
    if (L <= m) update(L, R, v, l, m, rt << 1);
    if (R > m) update(L, R, v, m + 1, r, rt << 1 | 1);
    pushUp(l, r, rt);
  }
  inline void pushDown(int l, int r, int rt) {
    if (add[rt]) {
      int m = (l + r) >> 1;
      int ls = rt << 1;
      int rs = rt << 1 | 1;
      add[ls] = (add[ls] + add[rt]) % mod;
      add[rs] = (add[rs] + add[rt]) % mod;
      Down(m - l + 1, ls, 0);
      Down(r - m, rs, 0);
      Down(m - l + 1, ls, 1);
      Down(r - m, rs, 1);
      add[rt] = 0;
    }
  }
  void build(int l = 1, int r = n, int rt = 1) {
    add[rt] = 0;
    if (l == r) {
      scanf("%lld", &sum[rt][0]);
      sum[rt][1] = sum[rt][0];
      return;
    }
    int m = (l + r) >> 1;
    build(l, m, rt << 1);
    build(m + 1, r, rt << 1 | 1);
    pushUp(l, r, rt);
  }
  void insert(int p, int v, int l = 1, int r = n, int rt = 1) {
    if (l == r) {
      sum[rt][0] = sum[rt][1] = v;
      return;
    }
    int m = (l + r) >> 1;
    pushDown(l, r, rt);
    if (p <= m)
      insert(p, v, l, m, rt << 1);
    else
      insert(p, v, m + 1, r, rt << 1 | 1);
    pushUp(l, r, rt);
  }
  inline long long shift(int x, int rt) {
    if (x <= 1) return sum[rt][x];
    return (f[x - 1] * sum[rt][1] % mod + f[x - 2] * sum[rt][0] % mod) % mod;
  }
  long long query(int L, int R, int l = 1, int r = n, int rt = 1) {
    if (L <= l && r <= R) {
      int len = r - l + 1;
      long long ret = shift(pos, rt);
      pos += len;
      return ret;
    }
    int m = (l + r) >> 1;
    pushDown(l, r, rt);
    long long ret = 0;
    if (L <= m) ret = (ret + query(L, R, l, m, rt << 1)) % mod;
    if (R > m) ret = (ret + query(L, R, m + 1, r, rt << 1 | 1)) % mod;
    return ret;
  }
} T;
int main() {
  int i, j;
  f[0] = f[1] = 1;
  for (i = 2; i < maxn; i++) f[i] = (f[i - 1] + f[i - 2]) % mod;
  int m;
  scanf("%d%d", &n, &m);
  T.build();
  while (m--) {
    int op, x, y;
    scanf("%d%d%d", &op, &x, &y);
    if (op == 1)
      T.insert(x, y);
    else if (op == 2) {
      pos = 0;
      printf("%lld\n", T.query(x, y));
    } else if (op == 3) {
      int z;
      scanf("%d", &z);
      T.update(x, y, z);
    }
  }
  return 0;
}

### Prompt

Your challenge is to write a Cpp solution 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;
const int maxn = 200005;
const int mod = 1e9;
long long f[maxn];
int n;
int pos;
struct segtree {
  long long sum[maxn << 2][2], add[maxn << 2];
  inline void pushUp(int l, int r, int rt) {
    int m = (l + r) >> 1;
    sum[rt][0] = (sum[rt << 1][0] + shift(m - l + 1, rt << 1 | 1)) % mod;
    sum[rt][1] = (sum[rt << 1][1] + shift(m - l + 2, rt << 1 | 1)) % mod;
  }
  inline void Down(int len, int rt, int kd) {
    long long tp;
    if (kd == 1) {
      tp = (f[len + 2] - 2 + mod) % mod;
    } else
      tp = (f[len + 1] - 1 + mod) % mod;
    tp = tp * add[rt] % mod * len % mod;
    sum[rt][kd] += tp;
    sum[rt][kd] %= mod;
  }
  inline void up(int len, int rt, int kd, int v) {
    long long tp;
    if (kd == 1) {
      tp = (f[len + 2] - 2 + mod) % mod;
    } else
      tp = (f[len + 1] - 1 + mod) % mod;
    tp = tp * v % mod * len % mod;
    sum[rt][kd] += tp;
    sum[rt][kd] %= mod;
  }
  void update(int L, int R, int v, int l = 1, int r = n, int rt = 1) {
    if (L <= l && r <= R) {
      add[rt] = (add[rt] + v) % mod;
      up(r - l + 1, rt, 0, v);
      up(r - l + 1, rt, 1, v);
      return;
    }
    int m = (l + r) >> 1;
    pushDown(l, r, rt);
    if (L <= m) update(L, R, v, l, m, rt << 1);
    if (R > m) update(L, R, v, m + 1, r, rt << 1 | 1);
    pushUp(l, r, rt);
  }
  inline void pushDown(int l, int r, int rt) {
    if (add[rt]) {
      int m = (l + r) >> 1;
      int ls = rt << 1;
      int rs = rt << 1 | 1;
      add[ls] = (add[ls] + add[rt]) % mod;
      add[rs] = (add[rs] + add[rt]) % mod;
      Down(m - l + 1, ls, 0);
      Down(r - m, rs, 0);
      Down(m - l + 1, ls, 1);
      Down(r - m, rs, 1);
      add[rt] = 0;
    }
  }
  void build(int l = 1, int r = n, int rt = 1) {
    add[rt] = 0;
    if (l == r) {
      scanf("%lld", &sum[rt][0]);
      sum[rt][1] = sum[rt][0];
      return;
    }
    int m = (l + r) >> 1;
    build(l, m, rt << 1);
    build(m + 1, r, rt << 1 | 1);
    pushUp(l, r, rt);
  }
  void insert(int p, int v, int l = 1, int r = n, int rt = 1) {
    if (l == r) {
      sum[rt][0] = sum[rt][1] = v;
      return;
    }
    int m = (l + r) >> 1;
    pushDown(l, r, rt);
    if (p <= m)
      insert(p, v, l, m, rt << 1);
    else
      insert(p, v, m + 1, r, rt << 1 | 1);
    pushUp(l, r, rt);
  }
  inline long long shift(int x, int rt) {
    if (x <= 1) return sum[rt][x];
    return (f[x - 1] * sum[rt][1] % mod + f[x - 2] * sum[rt][0] % mod) % mod;
  }
  long long query(int L, int R, int l = 1, int r = n, int rt = 1) {
    if (L <= l && r <= R) {
      int len = r - l + 1;
      long long ret = shift(pos, rt);
      pos += len;
      return ret;
    }
    int m = (l + r) >> 1;
    pushDown(l, r, rt);
    long long ret = 0;
    if (L <= m) ret = (ret + query(L, R, l, m, rt << 1)) % mod;
    if (R > m) ret = (ret + query(L, R, m + 1, r, rt << 1 | 1)) % mod;
    return ret;
  }
} T;
int main() {
  int i, j;
  f[0] = f[1] = 1;
  for (i = 2; i < maxn; i++) f[i] = (f[i - 1] + f[i - 2]) % mod;
  int m;
  scanf("%d%d", &n, &m);
  T.build();
  while (m--) {
    int op, x, y;
    scanf("%d%d%d", &op, &x, &y);
    if (op == 1)
      T.insert(x, y);
    else if (op == 2) {
      pos = 0;
      printf("%lld\n", T.query(x, y));
    } else if (op == 3) {
      int z;
      scanf("%d", &z);
      T.update(x, y, z);
    }
  }
  return 0;
}

```