#include <bits/stdc++.h>
using namespace std;
template <typename T>
void read(T &a) {
  register int b = 1, c;
  a = 0;
  for (c = fgetc(stdin); c > 57 || c < 48; c = fgetc(stdin))
    if (c == 45) b = -1;
  for (; c >= 48 && c <= 57; c = fgetc(stdin)) a = a * 10 + c - 48;
  a *= b;
}
struct mat {
  int x, y, arr[3][3];
  mat() : x(0), y(0) { arr[0][0] = arr[0][1] = arr[1][0] = arr[1][1] = 0; }
  inline void init(int a, int b) {
    x = a;
    y = b;
  }
  inline mat operator*(const mat &a) const {
    mat t;
    t.init(x, a.y);
    for (int i = 0; i < t.x; i++) {
      for (int j = 0; j < t.y; j++) {
        for (int k = 0; k < y; k++) {
          t.arr[i][j] =
              (((t.arr[i][j]) +
                (((1LL * (arr[i][k]) * (a.arr[k][j])) % 1000000000))) %
               1000000000);
        }
      }
    }
    return t;
  }
};
mat fib, pre[200005];
struct SEGT {
  int sz;
  struct node {
    int sum0, sum1, val, sz;
    node() : sum0(0), sum1(0), val(0) { sz = 0; }
    node(int a, int b) : sum0(a), sum1(b) {}
  };
  node nodes[4 * 200005];
  inline void init(int n) {
    for (sz = 1; sz <= n; sz <<= 1)
      ;
  }
  inline void pushup(node &a, node b, node c) {
    mat cur;
    cur.init(2, 1);
    cur.arr[0][0] = c.sum0;
    cur.arr[1][0] = c.sum1;
    mat matrix = pre[b.sz] * cur;
    a.sum0 = (((b.sum0) + (matrix.arr[0][0])) % 1000000000);
    a.sum1 = (((b.sum1) + (matrix.arr[1][0])) % 1000000000);
  }
  inline void pushup(int i) {
    if (i < sz) pushup(nodes[i], nodes[i << 1], nodes[i << 1 | 1]);
  }
  inline void build(int a, int b, int i, int n, int *arr) {
    if (b - a == 1) {
      nodes[i].val = nodes[i].sum0 = nodes[i].sum1 = arr[i - sz];
      nodes[i].sz = (i - sz) < n;
      return;
    }
    int m = (a + b) >> 1;
    build(a, m, i << 1, n, arr);
    build(m, b, i << 1 | 1, n, arr);
    nodes[i].sz = nodes[i << 1].sz + nodes[i << 1 | 1].sz;
    nodes[i].val =
        (((nodes[i << 1].val) + (nodes[i << 1 | 1].val)) % 1000000000);
    pushup(i);
  }
  inline void change(int i, int val) {
    i += sz - 1;
    nodes[i].val = nodes[i].sum0 = nodes[i].sum1 = val;
    while ((i >>= 1) >= 1) pushup(i);
  }
  inline node query(int a, int b, int i, int l, int r) {
    if (l <= a && b <= r) return nodes[i];
    if (r <= a || b <= l) return node();
    node x, y, ans;
    int m = (a + b) >> 1;
    x = query(a, m, i << 1, l, r);
    y = query(m, b, i << 1 | 1, l, r);
    ans.sz = x.sz + y.sz;
    pushup(ans, x, y);
    return ans;
  }
};
SEGT segt;
int n, q, arr[200005];
int main() {
  fib.init(2, 2);
  fib.arr[0][0] = 0;
  fib.arr[0][1] = 1;
  fib.arr[1][0] = 1;
  fib.arr[1][1] = 1;
  read(n);
  read(q);
  pre[0].init(2, 2);
  pre[0].arr[0][0] = 1;
  pre[0].arr[0][1] = 0;
  pre[0].arr[1][0] = 0;
  pre[0].arr[1][1] = 1;
  for (int i = 1; i <= n; i++) pre[i] = pre[i - 1] * fib;
  segt.init(n);
  for (int i = 0; i < n; i++) read(arr[i]);
  segt.build(0, segt.sz, 1, n, arr);
  while (q--) {
    int t;
    read(t);
    if (t == 1) {
      int a, b;
      read(a);
      read(b);
      segt.change(a, b);
    } else {
      int a, b;
      read(a);
      read(b);
      printf("%d\n", segt.query(0, segt.sz, 1, a - 1, b).sum0);
    }
  }
  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;
template <typename T>
void read(T &a) {
  register int b = 1, c;
  a = 0;
  for (c = fgetc(stdin); c > 57 || c < 48; c = fgetc(stdin))
    if (c == 45) b = -1;
  for (; c >= 48 && c <= 57; c = fgetc(stdin)) a = a * 10 + c - 48;
  a *= b;
}
struct mat {
  int x, y, arr[3][3];
  mat() : x(0), y(0) { arr[0][0] = arr[0][1] = arr[1][0] = arr[1][1] = 0; }
  inline void init(int a, int b) {
    x = a;
    y = b;
  }
  inline mat operator*(const mat &a) const {
    mat t;
    t.init(x, a.y);
    for (int i = 0; i < t.x; i++) {
      for (int j = 0; j < t.y; j++) {
        for (int k = 0; k < y; k++) {
          t.arr[i][j] =
              (((t.arr[i][j]) +
                (((1LL * (arr[i][k]) * (a.arr[k][j])) % 1000000000))) %
               1000000000);
        }
      }
    }
    return t;
  }
};
mat fib, pre[200005];
struct SEGT {
  int sz;
  struct node {
    int sum0, sum1, val, sz;
    node() : sum0(0), sum1(0), val(0) { sz = 0; }
    node(int a, int b) : sum0(a), sum1(b) {}
  };
  node nodes[4 * 200005];
  inline void init(int n) {
    for (sz = 1; sz <= n; sz <<= 1)
      ;
  }
  inline void pushup(node &a, node b, node c) {
    mat cur;
    cur.init(2, 1);
    cur.arr[0][0] = c.sum0;
    cur.arr[1][0] = c.sum1;
    mat matrix = pre[b.sz] * cur;
    a.sum0 = (((b.sum0) + (matrix.arr[0][0])) % 1000000000);
    a.sum1 = (((b.sum1) + (matrix.arr[1][0])) % 1000000000);
  }
  inline void pushup(int i) {
    if (i < sz) pushup(nodes[i], nodes[i << 1], nodes[i << 1 | 1]);
  }
  inline void build(int a, int b, int i, int n, int *arr) {
    if (b - a == 1) {
      nodes[i].val = nodes[i].sum0 = nodes[i].sum1 = arr[i - sz];
      nodes[i].sz = (i - sz) < n;
      return;
    }
    int m = (a + b) >> 1;
    build(a, m, i << 1, n, arr);
    build(m, b, i << 1 | 1, n, arr);
    nodes[i].sz = nodes[i << 1].sz + nodes[i << 1 | 1].sz;
    nodes[i].val =
        (((nodes[i << 1].val) + (nodes[i << 1 | 1].val)) % 1000000000);
    pushup(i);
  }
  inline void change(int i, int val) {
    i += sz - 1;
    nodes[i].val = nodes[i].sum0 = nodes[i].sum1 = val;
    while ((i >>= 1) >= 1) pushup(i);
  }
  inline node query(int a, int b, int i, int l, int r) {
    if (l <= a && b <= r) return nodes[i];
    if (r <= a || b <= l) return node();
    node x, y, ans;
    int m = (a + b) >> 1;
    x = query(a, m, i << 1, l, r);
    y = query(m, b, i << 1 | 1, l, r);
    ans.sz = x.sz + y.sz;
    pushup(ans, x, y);
    return ans;
  }
};
SEGT segt;
int n, q, arr[200005];
int main() {
  fib.init(2, 2);
  fib.arr[0][0] = 0;
  fib.arr[0][1] = 1;
  fib.arr[1][0] = 1;
  fib.arr[1][1] = 1;
  read(n);
  read(q);
  pre[0].init(2, 2);
  pre[0].arr[0][0] = 1;
  pre[0].arr[0][1] = 0;
  pre[0].arr[1][0] = 0;
  pre[0].arr[1][1] = 1;
  for (int i = 1; i <= n; i++) pre[i] = pre[i - 1] * fib;
  segt.init(n);
  for (int i = 0; i < n; i++) read(arr[i]);
  segt.build(0, segt.sz, 1, n, arr);
  while (q--) {
    int t;
    read(t);
    if (t == 1) {
      int a, b;
      read(a);
      read(b);
      segt.change(a, b);
    } else {
      int a, b;
      read(a);
      read(b);
      printf("%d\n", segt.query(0, segt.sz, 1, a - 1, b).sum0);
    }
  }
  return 0;
}

```