#include <bits/stdc++.h>
using namespace std;
inline long long read() {
  register long long x = 0, f = 1;
  register char c = getchar();
  while (c < '0' || c > '9') {
    if (c == '-') f = -1;
    c = getchar();
  }
  while (c >= '0' && c <= '9') x = x * 10 + c - 48, c = getchar();
  return x * f;
}
long long n, m, a[200005], f[200005], val1[200005 << 2], val[200005 << 2],
    tag[200005 << 2], sum[200005];
inline void updata(long long k, long long l, long long r) {
  val[k] = (val[k] + 1ll * tag[k] * sum[r - l] % 1000000000) % 1000000000;
  val1[k] =
      (val1[k] + 1ll * tag[k] * (sum[r - l + 1] - 1) % 1000000000) % 1000000000;
}
inline void pushdown(long long k, long long l, long long r) {
  if (tag[k] == 0) return;
  long long mid = (l + r) >> 1;
  tag[k * 2] = (tag[k * 2] + tag[k]) % 1000000000,
          tag[k * 2 + 1] = (tag[k * 2 + 1] + tag[k]) % 1000000000;
  updata(k * 2, l, mid), updata(k * 2 + 1, mid + 1, r), tag[k] = 0;
}
inline void pushup(long long k, long long l, long long r) {
  long long mid = (l + r) >> 1, d = mid - l + 1;
  val[k] = (val[k * 2] + (d >= 2) * f[d - 2] * val[k * 2 + 1] % 1000000000 +
            f[d - 1] * val1[k * 2 + 1] % 1000000000) %
           1000000000;
  val1[k] = (val1[k * 2] + f[d - 1] * val[k * 2 + 1] % 1000000000 +
             f[d] * val1[k * 2 + 1] % 1000000000) %
            1000000000;
}
inline void build(long long k, long long l, long long r) {
  if (l == r) return (void)(val[k] = val1[k] = a[l]);
  long long mid = (l + r) >> 1;
  build(k * 2, l, mid), build(k * 2 + 1, mid + 1, r), pushup(k, l, r);
}
inline void change(long long k, long long l, long long r, long long x,
                   long long v) {
  if (l == r) return (void)(val[k] = val1[k] = v);
  long long mid = (l + r) >> 1;
  pushdown(k, l, r);
  if (x <= mid)
    change(k * 2, l, mid, x, v);
  else
    change(k * 2 + 1, mid + 1, r, x, v);
  pushup(k, l, r);
}
inline long long query(long long k, long long l, long long r, long long ll,
                       long long rr) {
  if (l >= ll && r <= rr) {
    long long d = l - ll;
    if (d == 0) return val[k];
    if (d == 1) return val1[k];
    return (f[d - 2] * val[k] % 1000000000 + f[d - 1] * val1[k] % 1000000000) %
           1000000000;
  }
  long long mid = (l + r) >> 1, ans = 0;
  pushdown(k, l, r);
  if (ll <= mid) ans = query(k * 2, l, mid, ll, rr);
  if (mid < rr) ans = (ans + query(k * 2 + 1, mid + 1, r, ll, rr)) % 1000000000;
  return ans;
}
inline void add(long long k, long long l, long long r, long long ll,
                long long rr, long long v) {
  if (l >= ll && r <= rr) {
    tag[k] = (tag[k] + v) % 1000000000, updata(k, l, r);
    return;
  }
  long long mid = (l + r) >> 1;
  pushdown(k, l, r);
  if (ll <= mid) add(k * 2, l, mid, ll, rr, v);
  if (mid < rr) add(k * 2 + 1, mid + 1, r, ll, rr, v);
  pushup(k, l, r);
}
inline void init() {
  f[0] = f[1] = 1, sum[0] = 1, sum[1] = 2;
  for (register long long i = 2; i <= n + 1; ++i)
    f[i] = (f[i - 1] + f[i - 2]) % 1000000000,
    sum[i] = (sum[i - 1] + f[i]) % 1000000000;
}
signed main() {
  n = read(), m = read(), init();
  for (register long long i = 1; i <= n; ++i) a[i] = read();
  build(1, 1, n);
  for (register long long i = 1; i <= m; ++i) {
    long long opt = read(), l = read(), r = read();
    if (opt == 1)
      change(1, 1, n, l, r);
    else if (opt == 2)
      printf("%I64d\n", query(1, 1, n, l, r));
    else
      add(1, 1, n, l, r, read());
  }
  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 long long read() {
  register long long x = 0, f = 1;
  register char c = getchar();
  while (c < '0' || c > '9') {
    if (c == '-') f = -1;
    c = getchar();
  }
  while (c >= '0' && c <= '9') x = x * 10 + c - 48, c = getchar();
  return x * f;
}
long long n, m, a[200005], f[200005], val1[200005 << 2], val[200005 << 2],
    tag[200005 << 2], sum[200005];
inline void updata(long long k, long long l, long long r) {
  val[k] = (val[k] + 1ll * tag[k] * sum[r - l] % 1000000000) % 1000000000;
  val1[k] =
      (val1[k] + 1ll * tag[k] * (sum[r - l + 1] - 1) % 1000000000) % 1000000000;
}
inline void pushdown(long long k, long long l, long long r) {
  if (tag[k] == 0) return;
  long long mid = (l + r) >> 1;
  tag[k * 2] = (tag[k * 2] + tag[k]) % 1000000000,
          tag[k * 2 + 1] = (tag[k * 2 + 1] + tag[k]) % 1000000000;
  updata(k * 2, l, mid), updata(k * 2 + 1, mid + 1, r), tag[k] = 0;
}
inline void pushup(long long k, long long l, long long r) {
  long long mid = (l + r) >> 1, d = mid - l + 1;
  val[k] = (val[k * 2] + (d >= 2) * f[d - 2] * val[k * 2 + 1] % 1000000000 +
            f[d - 1] * val1[k * 2 + 1] % 1000000000) %
           1000000000;
  val1[k] = (val1[k * 2] + f[d - 1] * val[k * 2 + 1] % 1000000000 +
             f[d] * val1[k * 2 + 1] % 1000000000) %
            1000000000;
}
inline void build(long long k, long long l, long long r) {
  if (l == r) return (void)(val[k] = val1[k] = a[l]);
  long long mid = (l + r) >> 1;
  build(k * 2, l, mid), build(k * 2 + 1, mid + 1, r), pushup(k, l, r);
}
inline void change(long long k, long long l, long long r, long long x,
                   long long v) {
  if (l == r) return (void)(val[k] = val1[k] = v);
  long long mid = (l + r) >> 1;
  pushdown(k, l, r);
  if (x <= mid)
    change(k * 2, l, mid, x, v);
  else
    change(k * 2 + 1, mid + 1, r, x, v);
  pushup(k, l, r);
}
inline long long query(long long k, long long l, long long r, long long ll,
                       long long rr) {
  if (l >= ll && r <= rr) {
    long long d = l - ll;
    if (d == 0) return val[k];
    if (d == 1) return val1[k];
    return (f[d - 2] * val[k] % 1000000000 + f[d - 1] * val1[k] % 1000000000) %
           1000000000;
  }
  long long mid = (l + r) >> 1, ans = 0;
  pushdown(k, l, r);
  if (ll <= mid) ans = query(k * 2, l, mid, ll, rr);
  if (mid < rr) ans = (ans + query(k * 2 + 1, mid + 1, r, ll, rr)) % 1000000000;
  return ans;
}
inline void add(long long k, long long l, long long r, long long ll,
                long long rr, long long v) {
  if (l >= ll && r <= rr) {
    tag[k] = (tag[k] + v) % 1000000000, updata(k, l, r);
    return;
  }
  long long mid = (l + r) >> 1;
  pushdown(k, l, r);
  if (ll <= mid) add(k * 2, l, mid, ll, rr, v);
  if (mid < rr) add(k * 2 + 1, mid + 1, r, ll, rr, v);
  pushup(k, l, r);
}
inline void init() {
  f[0] = f[1] = 1, sum[0] = 1, sum[1] = 2;
  for (register long long i = 2; i <= n + 1; ++i)
    f[i] = (f[i - 1] + f[i - 2]) % 1000000000,
    sum[i] = (sum[i - 1] + f[i]) % 1000000000;
}
signed main() {
  n = read(), m = read(), init();
  for (register long long i = 1; i <= n; ++i) a[i] = read();
  build(1, 1, n);
  for (register long long i = 1; i <= m; ++i) {
    long long opt = read(), l = read(), r = read();
    if (opt == 1)
      change(1, 1, n, l, r);
    else if (opt == 2)
      printf("%I64d\n", query(1, 1, n, l, r));
    else
      add(1, 1, n, l, r, read());
  }
  return 0;
}

```