#include <bits/stdc++.h>
using namespace std;
inline int read() {
  static int r;
  static char c;
  r = 0, c = getchar();
  while (c < '0' || c > '9') c = getchar();
  while (c >= '0' && c <= '9') r = r * 10 + (c - '0'), c = getchar();
  return r;
}
template <typename T>
inline void print(T *a, int n) {
  for (int i = 1; i < n; ++i) cout << a[i] << " ";
  cout << a[n] << endl;
}
const int mod = (int)1e9;
struct matrix {
  int m[2][2];
  inline matrix operator*(const matrix &x) const {
    static matrix r;
    for (int i = 0; i < 2; ++i)
      for (int j = 0; j < 2; ++j) {
        r.m[i][j] = 0;
        for (int k = 0; k < 2; ++k)
          r.m[i][j] += (long long)m[i][k] * x.m[k][j] % mod;
        r.m[i][j] %= mod;
      }
    return r;
  }
  inline void print() {
    for (int i = 0; i < 2; ++i) {
      for (int __i = 0; __i != 2; ++__i) cout << m[i][__i] << " ";
      cout << endl;
    };
    cout << endl;
  }
} t[200000 + 1];
int f[200000 + 1], fs[200000 + 1], a[200000 + 1];
struct node {
  int w, w2, s, d;
} tree[200000 * 5];
inline int add(int x, int y) {
  x += y;
  if (x >= mod) x -= mod;
  return x;
}
inline node update(node l, node r) {
  static node ret;
  ret.s = l.s + r.s, ret.d = 0;
  ret.w = (l.w + (long long)r.w * t[l.s].m[0][0] +
           (long long)r.w2 * t[l.s].m[1][0]) %
          mod;
  ret.w2 = (l.w2 + (long long)r.w * t[l.s - 1].m[0][0] +
            (long long)r.w2 * t[l.s - 1].m[1][0]) %
           mod;
  return ret;
}
inline void applyDelta(int x, int v) {
  tree[x].d += v;
  tree[x].w = add(tree[x].w, (long long)v * fs[tree[x].s - 1] % mod);
  if (tree[x].s > 1)
    tree[x].w2 = add(tree[x].w2, (long long)v * fs[tree[x].s - 2] % mod);
}
inline void push(int x) {
  if (!tree[x].d) return;
  applyDelta(((x) << 1), tree[x].d);
  applyDelta(((x) << 1 | 1), tree[x].d);
  tree[x].d = 0;
}
void build(int x, int l, int r) {
  if (l == r) {
    tree[x].s = 1;
    tree[x].w = a[l], tree[x].w2 = 0;
    return;
  }
  int mid = l + r >> 1;
  build(((x) << 1), l, mid);
  build(((x) << 1 | 1), mid + 1, r);
  tree[x] = update(tree[((x) << 1)], tree[((x) << 1 | 1)]);
}
node query(int x, int l, int r, int s, int t) {
  if (l == s && r == t) return tree[x];
  push(x);
  int mid = l + r >> 1;
  if (t <= mid) return query(((x) << 1), l, mid, s, t);
  if (s > mid) return query(((x) << 1 | 1), mid + 1, r, s, t);
  return update(query(((x) << 1), l, mid, s, mid),
                query(((x) << 1 | 1), mid + 1, r, mid + 1, t));
}
void modify(int x, int l, int r, int s, int t, int v) {
  if (l == s && r == t) {
    applyDelta(x, v);
    return;
  }
  push(x);
  int mid = l + r >> 1;
  if (t <= mid)
    modify(((x) << 1), l, mid, s, t, v);
  else if (s > mid)
    modify(((x) << 1 | 1), mid + 1, r, s, t, v);
  else {
    modify(((x) << 1), l, mid, s, mid, v);
    modify(((x) << 1 | 1), mid + 1, r, mid + 1, t, v);
  }
  tree[x] = update(tree[((x) << 1)], tree[((x) << 1 | 1)]);
}
int n, m;
int main(int argc, char *argv[]) {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; ++i) scanf("%d", a + i);
  f[0] = f[1] = fs[0] = 1, fs[1] = 2;
  for (int i = 2; i <= n; ++i) {
    f[i] = add(f[i - 1], f[i - 2]);
    fs[i] = add(fs[i - 1], f[i]);
  }
  t[1].m[0][0] = t[1].m[0][1] = t[1].m[1][0] = 1, t[1].m[1][1] = 0;
  t[0] = t[1];
  for (int i = 2; i <= n; ++i) t[i] = t[i - 1] * t[1];
  build(1, 1, n);
  while (m--) {
    int l, r, p, v;
    scanf("%d", &p);
    if (p == 1) {
      scanf("%d%d", &p, &v);
      modify(1, 1, n, p, p, v - query(1, 1, n, p, p).w);
    } else if (p == 2) {
      scanf("%d%d", &l, &r);
      printf("%d\n", query(1, 1, n, l, r).w);
    } else {
      scanf("%d%d%d", &l, &r, &v);
      modify(1, 1, n, l, r, v);
    }
  }
  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;
inline int read() {
  static int r;
  static char c;
  r = 0, c = getchar();
  while (c < '0' || c > '9') c = getchar();
  while (c >= '0' && c <= '9') r = r * 10 + (c - '0'), c = getchar();
  return r;
}
template <typename T>
inline void print(T *a, int n) {
  for (int i = 1; i < n; ++i) cout << a[i] << " ";
  cout << a[n] << endl;
}
const int mod = (int)1e9;
struct matrix {
  int m[2][2];
  inline matrix operator*(const matrix &x) const {
    static matrix r;
    for (int i = 0; i < 2; ++i)
      for (int j = 0; j < 2; ++j) {
        r.m[i][j] = 0;
        for (int k = 0; k < 2; ++k)
          r.m[i][j] += (long long)m[i][k] * x.m[k][j] % mod;
        r.m[i][j] %= mod;
      }
    return r;
  }
  inline void print() {
    for (int i = 0; i < 2; ++i) {
      for (int __i = 0; __i != 2; ++__i) cout << m[i][__i] << " ";
      cout << endl;
    };
    cout << endl;
  }
} t[200000 + 1];
int f[200000 + 1], fs[200000 + 1], a[200000 + 1];
struct node {
  int w, w2, s, d;
} tree[200000 * 5];
inline int add(int x, int y) {
  x += y;
  if (x >= mod) x -= mod;
  return x;
}
inline node update(node l, node r) {
  static node ret;
  ret.s = l.s + r.s, ret.d = 0;
  ret.w = (l.w + (long long)r.w * t[l.s].m[0][0] +
           (long long)r.w2 * t[l.s].m[1][0]) %
          mod;
  ret.w2 = (l.w2 + (long long)r.w * t[l.s - 1].m[0][0] +
            (long long)r.w2 * t[l.s - 1].m[1][0]) %
           mod;
  return ret;
}
inline void applyDelta(int x, int v) {
  tree[x].d += v;
  tree[x].w = add(tree[x].w, (long long)v * fs[tree[x].s - 1] % mod);
  if (tree[x].s > 1)
    tree[x].w2 = add(tree[x].w2, (long long)v * fs[tree[x].s - 2] % mod);
}
inline void push(int x) {
  if (!tree[x].d) return;
  applyDelta(((x) << 1), tree[x].d);
  applyDelta(((x) << 1 | 1), tree[x].d);
  tree[x].d = 0;
}
void build(int x, int l, int r) {
  if (l == r) {
    tree[x].s = 1;
    tree[x].w = a[l], tree[x].w2 = 0;
    return;
  }
  int mid = l + r >> 1;
  build(((x) << 1), l, mid);
  build(((x) << 1 | 1), mid + 1, r);
  tree[x] = update(tree[((x) << 1)], tree[((x) << 1 | 1)]);
}
node query(int x, int l, int r, int s, int t) {
  if (l == s && r == t) return tree[x];
  push(x);
  int mid = l + r >> 1;
  if (t <= mid) return query(((x) << 1), l, mid, s, t);
  if (s > mid) return query(((x) << 1 | 1), mid + 1, r, s, t);
  return update(query(((x) << 1), l, mid, s, mid),
                query(((x) << 1 | 1), mid + 1, r, mid + 1, t));
}
void modify(int x, int l, int r, int s, int t, int v) {
  if (l == s && r == t) {
    applyDelta(x, v);
    return;
  }
  push(x);
  int mid = l + r >> 1;
  if (t <= mid)
    modify(((x) << 1), l, mid, s, t, v);
  else if (s > mid)
    modify(((x) << 1 | 1), mid + 1, r, s, t, v);
  else {
    modify(((x) << 1), l, mid, s, mid, v);
    modify(((x) << 1 | 1), mid + 1, r, mid + 1, t, v);
  }
  tree[x] = update(tree[((x) << 1)], tree[((x) << 1 | 1)]);
}
int n, m;
int main(int argc, char *argv[]) {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; ++i) scanf("%d", a + i);
  f[0] = f[1] = fs[0] = 1, fs[1] = 2;
  for (int i = 2; i <= n; ++i) {
    f[i] = add(f[i - 1], f[i - 2]);
    fs[i] = add(fs[i - 1], f[i]);
  }
  t[1].m[0][0] = t[1].m[0][1] = t[1].m[1][0] = 1, t[1].m[1][1] = 0;
  t[0] = t[1];
  for (int i = 2; i <= n; ++i) t[i] = t[i - 1] * t[1];
  build(1, 1, n);
  while (m--) {
    int l, r, p, v;
    scanf("%d", &p);
    if (p == 1) {
      scanf("%d%d", &p, &v);
      modify(1, 1, n, p, p, v - query(1, 1, n, p, p).w);
    } else if (p == 2) {
      scanf("%d%d", &l, &r);
      printf("%d\n", query(1, 1, n, l, r).w);
    } else {
      scanf("%d%d%d", &l, &r, &v);
      modify(1, 1, n, l, r, v);
    }
  }
  return 0;
}

```