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
#include <bits/stdc++.h>
#pragma comment(linker, "/STACK:512000000")
using namespace std;
template <class T>
inline T sqr(T x) {
  return x * x;
}
template <class T>
inline string tostr(const T &x) {
  stringstream ss;
  ss << x;
  return ss.str();
}
const double EPS = 1e-6;
const int INF = 1000 * 1000 * 1000;
const char CINF = 102;
const long long LINF = INF * 1ll * INF;
const double PI = 3.1415926535897932384626433832795;
long long gcd(long long a, long long b) { return a ? gcd(b % a, a) : b; }
unsigned int gcd(unsigned int a, unsigned int b) {
  return a ? gcd(b % a, a) : b;
}
const long long mod = INF;
long long fmat[210000][2][2];
long long fsum[210000];
long long tree[810000][3];
void pre(int a, int b, int k) {
  if (!tree[k][2]) return;
  long long v = tree[k][2];
  tree[k][2] = 0;
  (tree[k][0] += fsum[b - a] * v) %= mod;
  (tree[k][1] += (fsum[b - a + 1] + mod - 1) * v) %= mod;
  if (b == a + 1) return;
  (tree[k * 2 + 1][2] += v) %= mod;
  (tree[k * 2 + 2][2] += v) %= mod;
}
void post(int a, int b, int k) {
  int c = (a + b) / 2;
  pre(a, c, k * 2 + 1);
  pre(c, b, k * 2 + 2);
  tree[k][0] = (tree[k * 2 + 1][0] + tree[k * 2 + 2][0] * fmat[c - a][0][0] +
                tree[k * 2 + 2][1] * fmat[c - a][0][1]) %
               mod;
  tree[k][1] = (tree[k * 2 + 1][1] + tree[k * 2 + 2][0] * fmat[c - a][1][0] +
                tree[k * 2 + 2][1] * fmat[c - a][1][1]) %
               mod;
}
void add(int l, int r, long long v, int a, int b, int k) {
  if (b <= l || a >= r) return;
  if (a >= l && b <= r) {
    (tree[k][2] += v) %= mod;
    return;
  }
  pre(a, b, k);
  int c = (a + b) / 2;
  add(l, r, v, a, c, k * 2 + 1);
  add(l, r, v, c, b, k * 2 + 2);
  post(a, b, k);
}
long long getsum(int l, int r, int a, int b, int k) {
  if (b <= l || a >= r) return 0;
  pre(a, b, k);
  if (a >= l && b <= r) {
    long long *as = tree[k];
    long long *bs = fmat[a - l][0];
    return (as[0] * bs[0] + as[1] * bs[1]) % mod;
  }
  int c = (a + b) / 2;
  return (getsum(l, r, a, c, k * 2 + 1) + getsum(l, r, c, b, k * 2 + 2)) % mod;
}
long long ar[1000];
void brute_add(int a, int b, long long v) {
  for (int i = a; i < b; ++i) {
    (ar[i] += v) %= mod;
  }
}
long long brute_sum(int a, int b) {
  long long f1 = 1, f2 = 1;
  long long s = 0;
  for (int i = a; i < b; ++i) {
    (s += f1 * ar[i]) %= mod;
    long long t = f2;
    (f2 += f1) %= mod;
    f1 = t;
  }
  return s;
}
void stress() {
  for (int n = 3; n < 100; ++n) {
    for (int m = 1; m < 100; ++m) {
      cerr << n << ' ' << m << endl;
      for (int qqq = 0; qqq < (10000); ++qqq) {
        memset(ar, 0, sizeof(ar));
        memset(tree, 0, 10000);
        for (int q = 0; q < (m); ++q) {
          int a = rand() % n;
          int b = rand() % n;
          if (b < a) swap(a, b);
          ++b;
          if (rand() % 2 == 0) {
            int v = rand();
            brute_add(a, b, v);
            add(a, b, v, 0, n, 0);
          } else {
            long long br = brute_sum(a, b);
            long long r = getsum(a, b, 0, n, 0);
            if (r != br) {
              cout << "failed " << n << ' ' << m << ' ' << q << ": " << br
                   << " " << r << endl;
              return;
            }
          }
        }
      }
    }
  }
  cout << "passed" << endl;
}
int main() {
  {
    long long m[2][2] = {{1, 0}, {0, 1}};
    long long s = 0;
    for (int i = 0; i < (205000); ++i) {
      for (int a = 0; a < (2); ++a) {
        for (int b = 0; b < (2); ++b) {
          fmat[i][a][b] = m[a][b];
        }
      }
      fsum[i] = s;
      long long f = (m[0][0] + m[0][1]) % mod;
      (s += f) %= mod;
      m[0][0] = fmat[i][1][0];
      m[0][1] = fmat[i][1][1];
      m[1][0] = (fmat[i][0][0] + fmat[i][1][0]) % mod;
      m[1][1] = (fmat[i][0][1] + fmat[i][1][1]) % mod;
    }
  }
  int n, m;
  cin >> n >> m;
  for (int i = 0; i < (n); ++i) {
    int a;
    scanf("%d", &a);
    add(i, i + 1, a, 0, n, 0);
  }
  for (int i = 0; i < (m); ++i) {
    int t;
    scanf("%d", &t);
    if (t == 1) {
      int x, v;
      scanf("%d%d", &x, &v);
      --x;
      long long y = getsum(x, x + 1, 0, n, 0);
      add(x, x + 1, v - y + mod, 0, n, 0);
    } else if (t == 2) {
      int a, b;
      scanf("%d%d", &a, &b);
      --a;
      printf("%d\n", (int)getsum(a, b, 0, n, 0));
    } else {
      int a, b, v;
      scanf("%d%d%d", &a, &b, &v);
      --a;
      add(a, b, v, 0, n, 0);
    }
  }
  return 0;
}
