#include <bits/stdc++.h>
using namespace std;
template <typename T>
inline bool chkmin(T& a, T b) {
  return a > b ? a = b, 1 : 0;
}
template <typename T>
inline bool chkmax(T& a, T b) {
  return a < b ? a = b, 1 : 0;
}
int f[200010] = {1, 1}, t[524290], t2[524290], tl[524290], ta[524299];
int n, m, T = 1;
int get(int a, int b, int l, int r) {
  if (l == 1 && r == tl[a]) return t2[a];
  if (l != 0 || r != tl[a]) {
    if (r <= tl[a << 1]) return get(a << 1, b, l, r);
    if (l >= tl[a << 1])
      return get(a << 1 ^ 1, b, l - tl[a << 1], r - tl[a << 1]);
    else
      return (get(a << 1, b, l, tl[a << 1]) +
              get(a << 1 ^ 1, b + tl[a << 1] - l, 0, r - tl[a << 1])) %
             1000000000;
  }
  return ((long long)t[a] * f[b] + (long long)t2[a] * (b ? f[b - 1] : 0)) %
         1000000000;
}
void change(int a, int l, int r, int d) {}
int main() {
  for (int i = 1; ++i != 200010;) f[i] = (f[i - 1] + f[i - 2]) % 1000000000;
  {
    {
      char __next__char__;
      while (!isdigit(__next__char__ = getchar()))
        ;
      n = __next__char__ - 48;
      while (isdigit(__next__char__ = getchar()))
        n = n * 10 + __next__char__ - 48;
    };
    {
      char __next__char__;
      while (!isdigit(__next__char__ = getchar()))
        ;
      m = __next__char__ - 48;
      while (isdigit(__next__char__ = getchar()))
        m = m * 10 + __next__char__ - 48;
    };
  };
  while (T < n) T <<= 1;
  for (int i = -1; ++i != n; t2[i + T] = 0) {
    char __next__char__;
    while (!isdigit(__next__char__ = getchar()))
      ;
    t[i + T] = __next__char__ - 48;
    while (isdigit(__next__char__ = getchar()))
      t[i + T] = t[i + T] * 10 + __next__char__ - 48;
  };
  for (int i = T; i--;) tl[i + T] = 1;
  for (int i = T; --i;) {
    tl[i] = tl[i << 1] << 1;
    t[i] = (get(i << 1, 0, 0, tl[i << 1]) +
            get(i << 1 ^ 1, tl[i << 1], 0, tl[i << 1])) %
           1000000000;
    t2[i] = (get(i << 1, 0, 1, tl[i << 1]) +
             get(i << 1 ^ 1, tl[i << 1] - 1, 0, tl[i << 1])) %
            1000000000;
  }
  while (m--) {
    int x;
    {
      char __next__char__;
      while (!isdigit(__next__char__ = getchar()))
        ;
      x = __next__char__ - 48;
      while (isdigit(__next__char__ = getchar()))
        x = x * 10 + __next__char__ - 48;
    };
    if (x == 2) {
      int l, r;
      {
        {
          char __next__char__;
          while (!isdigit(__next__char__ = getchar()))
            ;
          l = __next__char__ - 48;
          while (isdigit(__next__char__ = getchar()))
            l = l * 10 + __next__char__ - 48;
        };
        {
          char __next__char__;
          while (!isdigit(__next__char__ = getchar()))
            ;
          r = __next__char__ - 48;
          while (isdigit(__next__char__ = getchar()))
            r = r * 10 + __next__char__ - 48;
        };
      };
      l--;
      printf("%d\n", get(1, 0, l, r));
    } else if (x == 1) {
      int i, v;
      {
        {
          char __next__char__;
          while (!isdigit(__next__char__ = getchar()))
            ;
          i = __next__char__ - 48;
          while (isdigit(__next__char__ = getchar()))
            i = i * 10 + __next__char__ - 48;
        };
        {
          char __next__char__;
          while (!isdigit(__next__char__ = getchar()))
            ;
          v = __next__char__ - 48;
          while (isdigit(__next__char__ = getchar()))
            v = v * 10 + __next__char__ - 48;
        };
      };
      i += T - 1;
      t[i] = v;
      while (i >>= 1) {
        t[i] = (get(i << 1, 0, 0, tl[i << 1]) +
                get(i << 1 ^ 1, tl[i << 1], 0, tl[i << 1])) %
               1000000000;
        t2[i] = (get(i << 1, 0, 1, tl[i << 1]) +
                 get(i << 1 ^ 1, tl[i << 1] - 1, 0, tl[i << 1])) %
                1000000000;
      }
    } else {
      int l, r, d;
      {
        {
          char __next__char__;
          while (!isdigit(__next__char__ = getchar()))
            ;
          l = __next__char__ - 48;
          while (isdigit(__next__char__ = getchar()))
            l = l * 10 + __next__char__ - 48;
        };
        {
          char __next__char__;
          while (!isdigit(__next__char__ = getchar()))
            ;
          r = __next__char__ - 48;
          while (isdigit(__next__char__ = getchar()))
            r = r * 10 + __next__char__ - 48;
        };
        {
          char __next__char__;
          while (!isdigit(__next__char__ = getchar()))
            ;
          d = __next__char__ - 48;
          while (isdigit(__next__char__ = getchar()))
            d = d * 10 + __next__char__ - 48;
        };
      };
    }
  }
  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>
inline bool chkmin(T& a, T b) {
  return a > b ? a = b, 1 : 0;
}
template <typename T>
inline bool chkmax(T& a, T b) {
  return a < b ? a = b, 1 : 0;
}
int f[200010] = {1, 1}, t[524290], t2[524290], tl[524290], ta[524299];
int n, m, T = 1;
int get(int a, int b, int l, int r) {
  if (l == 1 && r == tl[a]) return t2[a];
  if (l != 0 || r != tl[a]) {
    if (r <= tl[a << 1]) return get(a << 1, b, l, r);
    if (l >= tl[a << 1])
      return get(a << 1 ^ 1, b, l - tl[a << 1], r - tl[a << 1]);
    else
      return (get(a << 1, b, l, tl[a << 1]) +
              get(a << 1 ^ 1, b + tl[a << 1] - l, 0, r - tl[a << 1])) %
             1000000000;
  }
  return ((long long)t[a] * f[b] + (long long)t2[a] * (b ? f[b - 1] : 0)) %
         1000000000;
}
void change(int a, int l, int r, int d) {}
int main() {
  for (int i = 1; ++i != 200010;) f[i] = (f[i - 1] + f[i - 2]) % 1000000000;
  {
    {
      char __next__char__;
      while (!isdigit(__next__char__ = getchar()))
        ;
      n = __next__char__ - 48;
      while (isdigit(__next__char__ = getchar()))
        n = n * 10 + __next__char__ - 48;
    };
    {
      char __next__char__;
      while (!isdigit(__next__char__ = getchar()))
        ;
      m = __next__char__ - 48;
      while (isdigit(__next__char__ = getchar()))
        m = m * 10 + __next__char__ - 48;
    };
  };
  while (T < n) T <<= 1;
  for (int i = -1; ++i != n; t2[i + T] = 0) {
    char __next__char__;
    while (!isdigit(__next__char__ = getchar()))
      ;
    t[i + T] = __next__char__ - 48;
    while (isdigit(__next__char__ = getchar()))
      t[i + T] = t[i + T] * 10 + __next__char__ - 48;
  };
  for (int i = T; i--;) tl[i + T] = 1;
  for (int i = T; --i;) {
    tl[i] = tl[i << 1] << 1;
    t[i] = (get(i << 1, 0, 0, tl[i << 1]) +
            get(i << 1 ^ 1, tl[i << 1], 0, tl[i << 1])) %
           1000000000;
    t2[i] = (get(i << 1, 0, 1, tl[i << 1]) +
             get(i << 1 ^ 1, tl[i << 1] - 1, 0, tl[i << 1])) %
            1000000000;
  }
  while (m--) {
    int x;
    {
      char __next__char__;
      while (!isdigit(__next__char__ = getchar()))
        ;
      x = __next__char__ - 48;
      while (isdigit(__next__char__ = getchar()))
        x = x * 10 + __next__char__ - 48;
    };
    if (x == 2) {
      int l, r;
      {
        {
          char __next__char__;
          while (!isdigit(__next__char__ = getchar()))
            ;
          l = __next__char__ - 48;
          while (isdigit(__next__char__ = getchar()))
            l = l * 10 + __next__char__ - 48;
        };
        {
          char __next__char__;
          while (!isdigit(__next__char__ = getchar()))
            ;
          r = __next__char__ - 48;
          while (isdigit(__next__char__ = getchar()))
            r = r * 10 + __next__char__ - 48;
        };
      };
      l--;
      printf("%d\n", get(1, 0, l, r));
    } else if (x == 1) {
      int i, v;
      {
        {
          char __next__char__;
          while (!isdigit(__next__char__ = getchar()))
            ;
          i = __next__char__ - 48;
          while (isdigit(__next__char__ = getchar()))
            i = i * 10 + __next__char__ - 48;
        };
        {
          char __next__char__;
          while (!isdigit(__next__char__ = getchar()))
            ;
          v = __next__char__ - 48;
          while (isdigit(__next__char__ = getchar()))
            v = v * 10 + __next__char__ - 48;
        };
      };
      i += T - 1;
      t[i] = v;
      while (i >>= 1) {
        t[i] = (get(i << 1, 0, 0, tl[i << 1]) +
                get(i << 1 ^ 1, tl[i << 1], 0, tl[i << 1])) %
               1000000000;
        t2[i] = (get(i << 1, 0, 1, tl[i << 1]) +
                 get(i << 1 ^ 1, tl[i << 1] - 1, 0, tl[i << 1])) %
                1000000000;
      }
    } else {
      int l, r, d;
      {
        {
          char __next__char__;
          while (!isdigit(__next__char__ = getchar()))
            ;
          l = __next__char__ - 48;
          while (isdigit(__next__char__ = getchar()))
            l = l * 10 + __next__char__ - 48;
        };
        {
          char __next__char__;
          while (!isdigit(__next__char__ = getchar()))
            ;
          r = __next__char__ - 48;
          while (isdigit(__next__char__ = getchar()))
            r = r * 10 + __next__char__ - 48;
        };
        {
          char __next__char__;
          while (!isdigit(__next__char__ = getchar()))
            ;
          d = __next__char__ - 48;
          while (isdigit(__next__char__ = getchar()))
            d = d * 10 + __next__char__ - 48;
        };
      };
    }
  }
  return 0;
}

```