#include <bits/stdc++.h>
using namespace std;
const int MAX = int(2e5) + 10;
const long long MOD = 1000000000;
int N, M;
long long A[MAX];
long long fib[MAX];
struct node {
  int lo, hi, mit, len;
  long long sum1, sum2, lazy;
  node *left, *right;
  node(int lo, int hi) : lo(lo), hi(hi) {
    if (lo == hi) {
      left = right = NULL;
      sum1 = A[lo];
      sum2 = 0;
      lazy = 0;
      len = 1;
      return;
    }
    lazy = 0;
    len = hi - lo + 1;
    mit = (lo + hi) >> 1;
    left = new node(lo, mit);
    right = new node(mit + 1, hi);
    update();
  }
  long long get(int offset) {
    if (!offset) return sum1;
    long long ret = (fib[offset] * sum1 + fib[offset - 1] * sum2) % MOD;
    return ret;
  }
  void update() {
    sum1 = (left->sum1 + right->get(mit + 1 - lo)) % MOD;
    sum2 = (left->sum2 + right->get(mit - lo)) % MOD;
  }
  void relax() {
    if (!lazy) return;
    left->lazy += lazy;
    right->lazy += lazy;
    left->sum1 = (left->sum1 + lazy * (fib[left->len + 1] - 1)) % MOD;
    right->sum1 = (right->sum1 + lazy * (fib[right->len + 1] - 1)) % MOD;
    left->sum2 = (left->sum2 + lazy * (fib[left->len] - 1)) % MOD;
    right->sum2 = (right->sum2 + lazy * (fib[right->len] - 1)) % MOD;
    lazy = 0;
  }
  void put(int x, int v) {
    if (x < lo || hi < x) return;
    if (x == lo && x == hi) {
      sum1 = v;
      sum2 = 0;
      return;
    }
    relax();
    if (x <= mit)
      left->put(x, v);
    else
      right->put(x, v);
    update();
  }
  long long query(int a, int b) {
    if (b < lo || hi < a) return 0;
    if (a <= lo && hi <= b) return get(lo - a);
    relax();
    long long L = left->query(a, b);
    long long R = right->query(a, b);
    return (L + R) % MOD;
  }
  void modify(int a, int b, int d) {
    if (b < lo || hi < a) return;
    if (a <= lo && hi <= b) {
      lazy += d;
      sum1 = (sum1 + d * (fib[len + 1] - 1)) % MOD;
      sum2 = (sum2 + d * (fib[len] - 1)) % MOD;
      return;
    }
    relax();
    left->modify(a, b, d);
    right->modify(a, b, d);
    update();
  }
};
int main() {
  scanf("%d%d", &N, &M);
  for (int i = 0; i < N; i++) scanf("%I64d", A + i);
  fib[0] = fib[1] = 1;
  for (int i = 2; i <= N + 2; i++) fib[i] = (fib[i - 1] + fib[i - 2]) % MOD;
  node *root = new node(0, N - 1);
  int typ;
  while (M--) {
    scanf("%d", &typ);
    if (typ == 1) {
      int x, v;
      scanf("%d%d", &x, &v), x--;
      root->put(x, v);
    }
    if (typ == 2) {
      int l, r;
      scanf("%d%d", &l, &r), l--, r--;
      long long ans = root->query(l, r);
      printf("%I64d\n", ans);
    }
    if (typ == 3) {
      int l, r, d;
      scanf("%d%d%d", &l, &r, &d);
      root->modify(l, r, d);
    }
  }
  return 0;
}

### Prompt

Your task is to create 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 MAX = int(2e5) + 10;
const long long MOD = 1000000000;
int N, M;
long long A[MAX];
long long fib[MAX];
struct node {
  int lo, hi, mit, len;
  long long sum1, sum2, lazy;
  node *left, *right;
  node(int lo, int hi) : lo(lo), hi(hi) {
    if (lo == hi) {
      left = right = NULL;
      sum1 = A[lo];
      sum2 = 0;
      lazy = 0;
      len = 1;
      return;
    }
    lazy = 0;
    len = hi - lo + 1;
    mit = (lo + hi) >> 1;
    left = new node(lo, mit);
    right = new node(mit + 1, hi);
    update();
  }
  long long get(int offset) {
    if (!offset) return sum1;
    long long ret = (fib[offset] * sum1 + fib[offset - 1] * sum2) % MOD;
    return ret;
  }
  void update() {
    sum1 = (left->sum1 + right->get(mit + 1 - lo)) % MOD;
    sum2 = (left->sum2 + right->get(mit - lo)) % MOD;
  }
  void relax() {
    if (!lazy) return;
    left->lazy += lazy;
    right->lazy += lazy;
    left->sum1 = (left->sum1 + lazy * (fib[left->len + 1] - 1)) % MOD;
    right->sum1 = (right->sum1 + lazy * (fib[right->len + 1] - 1)) % MOD;
    left->sum2 = (left->sum2 + lazy * (fib[left->len] - 1)) % MOD;
    right->sum2 = (right->sum2 + lazy * (fib[right->len] - 1)) % MOD;
    lazy = 0;
  }
  void put(int x, int v) {
    if (x < lo || hi < x) return;
    if (x == lo && x == hi) {
      sum1 = v;
      sum2 = 0;
      return;
    }
    relax();
    if (x <= mit)
      left->put(x, v);
    else
      right->put(x, v);
    update();
  }
  long long query(int a, int b) {
    if (b < lo || hi < a) return 0;
    if (a <= lo && hi <= b) return get(lo - a);
    relax();
    long long L = left->query(a, b);
    long long R = right->query(a, b);
    return (L + R) % MOD;
  }
  void modify(int a, int b, int d) {
    if (b < lo || hi < a) return;
    if (a <= lo && hi <= b) {
      lazy += d;
      sum1 = (sum1 + d * (fib[len + 1] - 1)) % MOD;
      sum2 = (sum2 + d * (fib[len] - 1)) % MOD;
      return;
    }
    relax();
    left->modify(a, b, d);
    right->modify(a, b, d);
    update();
  }
};
int main() {
  scanf("%d%d", &N, &M);
  for (int i = 0; i < N; i++) scanf("%I64d", A + i);
  fib[0] = fib[1] = 1;
  for (int i = 2; i <= N + 2; i++) fib[i] = (fib[i - 1] + fib[i - 2]) % MOD;
  node *root = new node(0, N - 1);
  int typ;
  while (M--) {
    scanf("%d", &typ);
    if (typ == 1) {
      int x, v;
      scanf("%d%d", &x, &v), x--;
      root->put(x, v);
    }
    if (typ == 2) {
      int l, r;
      scanf("%d%d", &l, &r), l--, r--;
      long long ans = root->query(l, r);
      printf("%I64d\n", ans);
    }
    if (typ == 3) {
      int l, r, d;
      scanf("%d%d%d", &l, &r, &d);
      root->modify(l, r, d);
    }
  }
  return 0;
}

```