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 *a*<sub class="lower-index">1</sub>, *a*<sub class="lower-index">2</sub>, ..., *a*<sub class="lower-index">*n*</sub>. Your task is to perform on it *m* consecutive operations of the following type:
 1.  For given numbers *x*<sub class="lower-index">*i*</sub> and *v*<sub class="lower-index">*i*</sub> assign value *v*<sub class="lower-index">*i*</sub> to element *a*<sub class="lower-index">*x*<sub class="lower-index">*i*</sub></sub>. 1.  For given numbers *l*<sub class="lower-index">*i*</sub> and *r*<sub class="lower-index">*i*</sub> you've got to calculate sum <img align="middle" class="tex-formula" src="https://espresso.codeforces.com/1d7ff346cc22d72b468f0d5a8f2d7186003971d4.png" style="max-width: 100.0%;max-height: 100.0%;"/>, where *f*<sub class="lower-index">0</sub> = *f*<sub class="lower-index">1</sub> = 1 and at *i* ≥ 2: *f*<sub class="lower-index">*i*</sub> = *f*<sub class="lower-index">*i* - 1</sub> + *f*<sub class="lower-index">*i* - 2</sub>. 1.  For a group of three numbers *l*<sub class="lower-index">*i*</sub> *r*<sub class="lower-index">*i*</sub> *d*<sub class="lower-index">*i*</sub> you should increase value *a*<sub class="lower-index">*x*</sub> by *d*<sub class="lower-index">*i*</sub> for all *x* (*l*<sub class="lower-index">*i*</sub> ≤ *x* ≤ *r*<sub class="lower-index">*i*</sub>). 
Smart Beaver planned a tour around great Canadian lakes, so he asked you to help him solve the given problem.
The first line contains two integers *n* and *m* (1 ≤ *n*, *m* ≤ 2·10<sup class="upper-index">5</sup>) — the number of integers in the sequence and the number of operations, correspondingly. The second line contains *n* integers *a*<sub class="lower-index">1</sub>, *a*<sub class="lower-index">2</sub>, ..., *a*<sub class="lower-index">*n*</sub> (0 ≤ *a*<sub class="lower-index">*i*</sub> ≤ 10<sup class="upper-index">5</sup>). Then follow *m* lines, each describes an operation. Each line starts with an integer *t*<sub class="lower-index">*i*</sub> (1 ≤ *t*<sub class="lower-index">*i*</sub> ≤ 3) — the operation type: 
 -  if *t*<sub class="lower-index">*i*</sub> = 1, then next follow two integers *x*<sub class="lower-index">*i*</sub> *v*<sub class="lower-index">*i*</sub> (1 ≤ *x*<sub class="lower-index">*i*</sub> ≤ *n*, 0 ≤ *v*<sub class="lower-index">*i*</sub> ≤ 10<sup class="upper-index">5</sup>); -  if *t*<sub class="lower-index">*i*</sub> = 2, then next follow two integers *l*<sub class="lower-index">*i*</sub> *r*<sub class="lower-index">*i*</sub> (1 ≤ *l*<sub class="lower-index">*i*</sub> ≤ *r*<sub class="lower-index">*i*</sub> ≤ *n*); -  if *t*<sub class="lower-index">*i*</sub> = 3, then next follow three integers *l*<sub class="lower-index">*i*</sub> *r*<sub class="lower-index">*i*</sub> *d*<sub class="lower-index">*i*</sub> (1 ≤ *l*<sub class="lower-index">*i*</sub> ≤ *r*<sub class="lower-index">*i*</sub> ≤ *n*, 0 ≤ *d*<sub class="lower-index">*i*</sub> ≤ 10<sup class="upper-index">5</sup>). 
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.
n,m = map(int, input().split())
a = list(map(int, input().split()))
f = [1]*n
for i in range(2,n):
    f[i] = f[i-1]+f[i-2]
for i in range(m):
    t,l,r = map(int, input().split())
    if t==1:
        a[l-1] = r
    else:
        sum_lr = 0
        for x in range(r-l+1):
            sum_lr += f[x] * a[l+x-1]
        print(sum_lr%1000000000)
