#include <bits/stdc++.h>
using namespace std;
__inline bool nextInt(int &val) {
  char ch;
  int sgn = 1;
  while ((ch = getchar()) != EOF) {
    if (ch == '-') sgn = -1;
    if (ch >= '0' && ch <= '9') break;
  }
  if (ch == EOF) return false;
  val = (int)(ch - '0');
  while (true) {
    ch = getchar();
    if (ch >= '0' && ch <= '9') {
      val = 10 * val + (int)(ch - '0');
    } else
      break;
  }
  val *= sgn;
  return true;
}
__inline bool nextString(string &s) {
  char ch;
  while ((ch = getchar()) != EOF) {
    if (ch >= 33 && ch <= 126) break;
  }
  if (ch == EOF) return false;
  s = string(1, ch);
  while (true) {
    ch = getchar();
    if (ch >= 33 && ch <= 126) {
      s = s + string(1, ch);
    } else
      break;
  }
  return true;
}
int n, q, v[333888], modul = 1000000000;
long long s0[5 * 333888], s1[5 * 333888], inc[5 * 333888];
int fa[333888], fb[333888], fc[333888], fd[333888], fib[333888], sfib[333888];
void init(int idx = 1, int l = 0, int r = n - 1) {
  if (l > r) return;
  if (l == r) {
    s0[idx] = s1[idx] = v[l];
    inc[idx] = 0;
  } else {
    int lid = idx + idx, rid = lid + 1, mid = (l + r) / 2;
    init(lid, l, mid);
    init(rid, mid + 1, r);
    s0[idx] = (s0[lid] +
               ((mid - l + 1) == 0
                    ? s0[rid]
                    : ((mid - l + 1) == 1 ? s1[rid]
                                          : (((((long long)(fb[mid - l + 1])) *
                                               ((long long)(s0[rid]))) %
                                              modul) +
                                             ((((long long)(fa[mid - l + 1])) *
                                               ((long long)(s1[rid]))) %
                                              modul)) %
                                                modul))) %
              modul;
    s1[idx] = (s1[lid] +
               ((mid - l + 2) == 0
                    ? s0[rid]
                    : ((mid - l + 2) == 1 ? s1[rid]
                                          : (((((long long)(fb[mid - l + 2])) *
                                               ((long long)(s0[rid]))) %
                                              modul) +
                                             ((((long long)(fa[mid - l + 2])) *
                                               ((long long)(s1[rid]))) %
                                              modul)) %
                                                modul))) %
              modul;
    inc[idx] = 0;
  }
}
void update(int comm, int ql, int qr, int val, int idx = 1, int l = 0,
            int r = n - 1) {
  if (l > r || ql > qr || qr < l || ql > r) return;
  if (ql <= l && r <= qr) {
    if (comm == 1) {
      s0[idx] = s1[idx] = val;
    } else {
      inc[idx] = (inc[idx] + val) % modul;
    }
  } else {
    int lid = idx + idx, rid = lid + 1, mid = (l + r) / 2;
    if (comm == 1) {
      val = (val + modul - inc[idx]) % modul;
    }
    update(comm, ql, qr, val, lid, l, mid);
    update(comm, ql, qr, val, rid, mid + 1, r);
    s0[idx] =
        (s0[lid] +
         ((((long long)(inc[lid])) *
           ((long long)(((0) > (mid - l)
                             ? 0
                             : (((mid - l) >= 0 ? sfib[mid - l] : 0) + modul -
                                (((0) - 1) >= 0 ? sfib[(0) - 1] : 0)) %
                                   modul)))) %
          modul) +
         ((mid - l + 1) == 0
              ? s0[rid]
              : ((mid - l + 1) == 1 ? s1[rid]
                                    : (((((long long)(fb[mid - l + 1])) *
                                         ((long long)(s0[rid]))) %
                                        modul) +
                                       ((((long long)(fa[mid - l + 1])) *
                                         ((long long)(s1[rid]))) %
                                        modul)) %
                                          modul)) +
         ((((long long)(inc[rid])) *
           ((long long)((
               (mid - l + 1) > (r - l)
                   ? 0
                   : (((r - l) >= 0 ? sfib[r - l] : 0) + modul -
                      (((mid - l + 1) - 1) >= 0 ? sfib[(mid - l + 1) - 1]
                                                : 0)) %
                         modul)))) %
          modul)) %
        modul;
    s1[idx] =
        (s1[lid] +
         ((((long long)(inc[lid])) *
           ((long long)(((1) > (mid - l + 1)
                             ? 0
                             : (((mid - l + 1) >= 0 ? sfib[mid - l + 1] : 0) +
                                modul - (((1) - 1) >= 0 ? sfib[(1) - 1] : 0)) %
                                   modul)))) %
          modul) +
         ((mid - l + 2) == 0
              ? s0[rid]
              : ((mid - l + 2) == 1 ? s1[rid]
                                    : (((((long long)(fb[mid - l + 2])) *
                                         ((long long)(s0[rid]))) %
                                        modul) +
                                       ((((long long)(fa[mid - l + 2])) *
                                         ((long long)(s1[rid]))) %
                                        modul)) %
                                          modul)) +
         ((((long long)(inc[rid])) *
           ((long long)((
               (mid - l + 2) > (r - l + 1)
                   ? 0
                   : (((r - l + 1) >= 0 ? sfib[r - l + 1] : 0) + modul -
                      (((mid - l + 2) - 1) >= 0 ? sfib[(mid - l + 2) - 1]
                                                : 0)) %
                         modul)))) %
          modul)) %
        modul;
  }
}
void query(int ql, int qr, long long &q0, long long &q1, int &cnt, int idx = 1,
           int l = 0, int r = n - 1) {
  if (ql > qr || l > r || qr < l || ql > r) {
    q0 = q1 = 0;
    cnt = 0;
    return;
  }
  if (ql <= l && r <= qr) {
    q0 = (s0[idx] +
          ((((long long)(inc[idx])) *
            ((long long)(((0) > (r - l)
                              ? 0
                              : (((r - l) >= 0 ? sfib[r - l] : 0) + modul -
                                 (((0) - 1) >= 0 ? sfib[(0) - 1] : 0)) %
                                    modul)))) %
           modul)) %
         modul;
    q1 = (s1[idx] +
          ((((long long)(inc[idx])) *
            ((long long)(((1) > (r - l + 1)
                              ? 0
                              : (((r - l + 1) >= 0 ? sfib[r - l + 1] : 0) +
                                 modul - (((1) - 1) >= 0 ? sfib[(1) - 1] : 0)) %
                                    modul)))) %
           modul)) %
         modul;
    cnt = r - l + 1;
  } else {
    long long ql0, ql1, qr0, qr1;
    int lid = idx + idx, rid = lid + 1, mid = (l + r) / 2, qlc, qrc;
    query(ql, qr, ql0, ql1, qlc, lid, l, mid);
    query(ql, qr, qr0, qr1, qrc, rid, mid + 1, r);
    q0 = (ql0 +
          ((qlc) == 0
               ? qr0
               : ((qlc) == 1 ? qr1
                             : (((((long long)(fb[qlc])) * ((long long)(qr0))) %
                                 modul) +
                                ((((long long)(fa[qlc])) * ((long long)(qr1))) %
                                 modul)) %
                                   modul)) +
          ((((long long)(inc[idx])) *
            ((long long)((
                (0) > (qlc + qrc - 1)
                    ? 0
                    : (((qlc + qrc - 1) >= 0 ? sfib[qlc + qrc - 1] : 0) +
                       modul - (((0) - 1) >= 0 ? sfib[(0) - 1] : 0)) %
                          modul)))) %
           modul)) %
         modul;
    q1 = (ql1 +
          ((qlc + 1) == 0
               ? qr0
               : ((qlc + 1) == 1
                      ? qr1
                      : (((((long long)(fb[qlc + 1])) * ((long long)(qr0))) %
                          modul) +
                         ((((long long)(fa[qlc + 1])) * ((long long)(qr1))) %
                          modul)) %
                            modul)) +
          ((((long long)(inc[idx])) *
            ((long long)(((1) > (qlc + qrc)
                              ? 0
                              : (((qlc + qrc) >= 0 ? sfib[qlc + qrc] : 0) +
                                 modul - (((1) - 1) >= 0 ? sfib[(1) - 1] : 0)) %
                                    modul)))) %
           modul)) %
         modul;
    cnt = qlc + qrc;
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  fib[0] = fib[1] = 1;
  sfib[0] = 1;
  sfib[1] = 2;
  for (int i = (2); i < (333888); i++) {
    fib[i] = (fib[i - 1] + fib[i - 2]) % modul;
    sfib[i] = (sfib[i - 1] + fib[i]) % modul;
  }
  memset(fa, 0, sizeof(fa));
  ;
  memset(fb, 0, sizeof(fb));
  ;
  memset(fc, 0, sizeof(fc));
  ;
  memset(fd, 0, sizeof(fd));
  ;
  fb[0] = 1;
  fa[1] = 1;
  fa[2] = fb[2] = fc[2] = 1;
  for (int i = (3); i < (333888); i++) {
    fa[i] = (fa[i - 1] + fc[i - 1]) % modul;
    fb[i] = (fb[i - 1] + fd[i - 1]) % modul;
    fc[i] = fa[i - 1];
    fd[i] = fb[i - 1];
  }
  scanf("%d%d", &n, &q);
  for (int i = 0; i < (n); i++) scanf("%d", v + i);
  init();
  int comm, idx, ql, qr, val;
  for (int iq = 0; iq < (q); iq++) {
    scanf("%d", &comm);
    if (comm == 1) {
      scanf("%d%d", &idx, &val);
      idx--;
      update(comm, idx, idx, val);
    } else if (comm == 2) {
      scanf("%d%d", &ql, &qr);
      ql--;
      qr--;
      long long ret0, ret1;
      int cnt;
      query(ql, qr, ret0, ret1, cnt);
      printf("%d\n", (int)ret0);
    } else {
      scanf("%d%d%d", &ql, &qr, &val);
      ql--;
      qr--;
      update(comm, ql, qr, val);
    }
  }
  return 0;
}

### Prompt

Develop a solution in Cpp 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 bool nextInt(int &val) {
  char ch;
  int sgn = 1;
  while ((ch = getchar()) != EOF) {
    if (ch == '-') sgn = -1;
    if (ch >= '0' && ch <= '9') break;
  }
  if (ch == EOF) return false;
  val = (int)(ch - '0');
  while (true) {
    ch = getchar();
    if (ch >= '0' && ch <= '9') {
      val = 10 * val + (int)(ch - '0');
    } else
      break;
  }
  val *= sgn;
  return true;
}
__inline bool nextString(string &s) {
  char ch;
  while ((ch = getchar()) != EOF) {
    if (ch >= 33 && ch <= 126) break;
  }
  if (ch == EOF) return false;
  s = string(1, ch);
  while (true) {
    ch = getchar();
    if (ch >= 33 && ch <= 126) {
      s = s + string(1, ch);
    } else
      break;
  }
  return true;
}
int n, q, v[333888], modul = 1000000000;
long long s0[5 * 333888], s1[5 * 333888], inc[5 * 333888];
int fa[333888], fb[333888], fc[333888], fd[333888], fib[333888], sfib[333888];
void init(int idx = 1, int l = 0, int r = n - 1) {
  if (l > r) return;
  if (l == r) {
    s0[idx] = s1[idx] = v[l];
    inc[idx] = 0;
  } else {
    int lid = idx + idx, rid = lid + 1, mid = (l + r) / 2;
    init(lid, l, mid);
    init(rid, mid + 1, r);
    s0[idx] = (s0[lid] +
               ((mid - l + 1) == 0
                    ? s0[rid]
                    : ((mid - l + 1) == 1 ? s1[rid]
                                          : (((((long long)(fb[mid - l + 1])) *
                                               ((long long)(s0[rid]))) %
                                              modul) +
                                             ((((long long)(fa[mid - l + 1])) *
                                               ((long long)(s1[rid]))) %
                                              modul)) %
                                                modul))) %
              modul;
    s1[idx] = (s1[lid] +
               ((mid - l + 2) == 0
                    ? s0[rid]
                    : ((mid - l + 2) == 1 ? s1[rid]
                                          : (((((long long)(fb[mid - l + 2])) *
                                               ((long long)(s0[rid]))) %
                                              modul) +
                                             ((((long long)(fa[mid - l + 2])) *
                                               ((long long)(s1[rid]))) %
                                              modul)) %
                                                modul))) %
              modul;
    inc[idx] = 0;
  }
}
void update(int comm, int ql, int qr, int val, int idx = 1, int l = 0,
            int r = n - 1) {
  if (l > r || ql > qr || qr < l || ql > r) return;
  if (ql <= l && r <= qr) {
    if (comm == 1) {
      s0[idx] = s1[idx] = val;
    } else {
      inc[idx] = (inc[idx] + val) % modul;
    }
  } else {
    int lid = idx + idx, rid = lid + 1, mid = (l + r) / 2;
    if (comm == 1) {
      val = (val + modul - inc[idx]) % modul;
    }
    update(comm, ql, qr, val, lid, l, mid);
    update(comm, ql, qr, val, rid, mid + 1, r);
    s0[idx] =
        (s0[lid] +
         ((((long long)(inc[lid])) *
           ((long long)(((0) > (mid - l)
                             ? 0
                             : (((mid - l) >= 0 ? sfib[mid - l] : 0) + modul -
                                (((0) - 1) >= 0 ? sfib[(0) - 1] : 0)) %
                                   modul)))) %
          modul) +
         ((mid - l + 1) == 0
              ? s0[rid]
              : ((mid - l + 1) == 1 ? s1[rid]
                                    : (((((long long)(fb[mid - l + 1])) *
                                         ((long long)(s0[rid]))) %
                                        modul) +
                                       ((((long long)(fa[mid - l + 1])) *
                                         ((long long)(s1[rid]))) %
                                        modul)) %
                                          modul)) +
         ((((long long)(inc[rid])) *
           ((long long)((
               (mid - l + 1) > (r - l)
                   ? 0
                   : (((r - l) >= 0 ? sfib[r - l] : 0) + modul -
                      (((mid - l + 1) - 1) >= 0 ? sfib[(mid - l + 1) - 1]
                                                : 0)) %
                         modul)))) %
          modul)) %
        modul;
    s1[idx] =
        (s1[lid] +
         ((((long long)(inc[lid])) *
           ((long long)(((1) > (mid - l + 1)
                             ? 0
                             : (((mid - l + 1) >= 0 ? sfib[mid - l + 1] : 0) +
                                modul - (((1) - 1) >= 0 ? sfib[(1) - 1] : 0)) %
                                   modul)))) %
          modul) +
         ((mid - l + 2) == 0
              ? s0[rid]
              : ((mid - l + 2) == 1 ? s1[rid]
                                    : (((((long long)(fb[mid - l + 2])) *
                                         ((long long)(s0[rid]))) %
                                        modul) +
                                       ((((long long)(fa[mid - l + 2])) *
                                         ((long long)(s1[rid]))) %
                                        modul)) %
                                          modul)) +
         ((((long long)(inc[rid])) *
           ((long long)((
               (mid - l + 2) > (r - l + 1)
                   ? 0
                   : (((r - l + 1) >= 0 ? sfib[r - l + 1] : 0) + modul -
                      (((mid - l + 2) - 1) >= 0 ? sfib[(mid - l + 2) - 1]
                                                : 0)) %
                         modul)))) %
          modul)) %
        modul;
  }
}
void query(int ql, int qr, long long &q0, long long &q1, int &cnt, int idx = 1,
           int l = 0, int r = n - 1) {
  if (ql > qr || l > r || qr < l || ql > r) {
    q0 = q1 = 0;
    cnt = 0;
    return;
  }
  if (ql <= l && r <= qr) {
    q0 = (s0[idx] +
          ((((long long)(inc[idx])) *
            ((long long)(((0) > (r - l)
                              ? 0
                              : (((r - l) >= 0 ? sfib[r - l] : 0) + modul -
                                 (((0) - 1) >= 0 ? sfib[(0) - 1] : 0)) %
                                    modul)))) %
           modul)) %
         modul;
    q1 = (s1[idx] +
          ((((long long)(inc[idx])) *
            ((long long)(((1) > (r - l + 1)
                              ? 0
                              : (((r - l + 1) >= 0 ? sfib[r - l + 1] : 0) +
                                 modul - (((1) - 1) >= 0 ? sfib[(1) - 1] : 0)) %
                                    modul)))) %
           modul)) %
         modul;
    cnt = r - l + 1;
  } else {
    long long ql0, ql1, qr0, qr1;
    int lid = idx + idx, rid = lid + 1, mid = (l + r) / 2, qlc, qrc;
    query(ql, qr, ql0, ql1, qlc, lid, l, mid);
    query(ql, qr, qr0, qr1, qrc, rid, mid + 1, r);
    q0 = (ql0 +
          ((qlc) == 0
               ? qr0
               : ((qlc) == 1 ? qr1
                             : (((((long long)(fb[qlc])) * ((long long)(qr0))) %
                                 modul) +
                                ((((long long)(fa[qlc])) * ((long long)(qr1))) %
                                 modul)) %
                                   modul)) +
          ((((long long)(inc[idx])) *
            ((long long)((
                (0) > (qlc + qrc - 1)
                    ? 0
                    : (((qlc + qrc - 1) >= 0 ? sfib[qlc + qrc - 1] : 0) +
                       modul - (((0) - 1) >= 0 ? sfib[(0) - 1] : 0)) %
                          modul)))) %
           modul)) %
         modul;
    q1 = (ql1 +
          ((qlc + 1) == 0
               ? qr0
               : ((qlc + 1) == 1
                      ? qr1
                      : (((((long long)(fb[qlc + 1])) * ((long long)(qr0))) %
                          modul) +
                         ((((long long)(fa[qlc + 1])) * ((long long)(qr1))) %
                          modul)) %
                            modul)) +
          ((((long long)(inc[idx])) *
            ((long long)(((1) > (qlc + qrc)
                              ? 0
                              : (((qlc + qrc) >= 0 ? sfib[qlc + qrc] : 0) +
                                 modul - (((1) - 1) >= 0 ? sfib[(1) - 1] : 0)) %
                                    modul)))) %
           modul)) %
         modul;
    cnt = qlc + qrc;
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  fib[0] = fib[1] = 1;
  sfib[0] = 1;
  sfib[1] = 2;
  for (int i = (2); i < (333888); i++) {
    fib[i] = (fib[i - 1] + fib[i - 2]) % modul;
    sfib[i] = (sfib[i - 1] + fib[i]) % modul;
  }
  memset(fa, 0, sizeof(fa));
  ;
  memset(fb, 0, sizeof(fb));
  ;
  memset(fc, 0, sizeof(fc));
  ;
  memset(fd, 0, sizeof(fd));
  ;
  fb[0] = 1;
  fa[1] = 1;
  fa[2] = fb[2] = fc[2] = 1;
  for (int i = (3); i < (333888); i++) {
    fa[i] = (fa[i - 1] + fc[i - 1]) % modul;
    fb[i] = (fb[i - 1] + fd[i - 1]) % modul;
    fc[i] = fa[i - 1];
    fd[i] = fb[i - 1];
  }
  scanf("%d%d", &n, &q);
  for (int i = 0; i < (n); i++) scanf("%d", v + i);
  init();
  int comm, idx, ql, qr, val;
  for (int iq = 0; iq < (q); iq++) {
    scanf("%d", &comm);
    if (comm == 1) {
      scanf("%d%d", &idx, &val);
      idx--;
      update(comm, idx, idx, val);
    } else if (comm == 2) {
      scanf("%d%d", &ql, &qr);
      ql--;
      qr--;
      long long ret0, ret1;
      int cnt;
      query(ql, qr, ret0, ret1, cnt);
      printf("%d\n", (int)ret0);
    } else {
      scanf("%d%d%d", &ql, &qr, &val);
      ql--;
      qr--;
      update(comm, ql, qr, val);
    }
  }
  return 0;
}

```