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_1, a_2, ..., a_{n}. Your task is to perform on it m consecutive operations of the following type:  For given numbers x_{i} and v_{i} assign value v_{i} to element a_{x}_{i}.  For given numbers l_{i} and r_{i} you've got to calculate sum $\sum_{x = 0}^{r_{i} - l_{i}}(f_{x} \cdot a_{l_{i} + x})$, where f_0 = f_1 = 1 and at i ≥ 2: f_{i} = f_{i} - 1 + f_{i} - 2.  For a group of three numbers l_{i} r_{i} d_{i} you should increase value a_{x} by d_{i} for all x (l_{i} ≤ x ≤ r_{i}). 

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·10^5) — the number of integers in the sequence and the number of operations, correspondingly. The second line contains n integers a_1, a_2, ..., a_{n} (0 ≤ a_{i} ≤ 10^5). Then follow m lines, each describes an operation. Each line starts with an integer t_{i} (1 ≤ t_{i} ≤ 3) — the operation type:   if t_{i} = 1, then next follow two integers x_{i} v_{i} (1 ≤ x_{i} ≤ n, 0 ≤ v_{i} ≤ 10^5);  if t_{i} = 2, then next follow two integers l_{i} r_{i} (1 ≤ l_{i} ≤ r_{i} ≤ n);  if t_{i} = 3, then next follow three integers l_{i} r_{i} d_{i} (1 ≤ l_{i} ≤ r_{i} ≤ n, 0 ≤ d_{i} ≤ 10^5). 

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 (10^9).


-----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

Difficulty: interview

Starter code:

Solutions:
from sys import *
from math import *

mod = 1000000000
f = [0 for i in range(200)]
f[0] = f[1] = 1
for i in range(2, 200):
  f[i] = f[i - 1] + f[i - 2]
n, m = stdin.readline().split()
n = int(n)
m = int(m)
a = list(map(int, stdin.readline().split()))
for i in range(m):
  tp, x, y = stdin.readline().split()
  tp = int(tp)
  x = int(x)
  y = int(y)
  if tp == 1:
    x -= 1
    a[x] = y
  else:
    s = 0
    x -= 1
    y -= 1
    for p in range(y - x + 1):
      s += f[p] * a[x + p]
    print(s % mod)




n, m = list(map(int, input().split()))
a = list(map(int, input().split()))

for i in range(m):
    t, l, r = list(map(int, input().split()))
    if t == 1:
        a[l-1] = r
    else:
        s = 0
        fiba = fibb = 1
        for i in range(l-1, r):
            s += fiba * a[i]
            fiba, fibb = fibb, fiba + fibb
        print(s % 1000000000)


n,m = list(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 = list(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)


n,m = list(map(int,input().split()))
d = [int(x) for x in input().split()]
f = [1,1]
for i in range(n):
    f.append((f[-1]+f[-2])% 1000000000)
for i in range(m):
    s = [int(x) for x in input().split()]
    if s[0] == 1:
        x = s[1]-1
        v = s[2]
        d[x] = v
    elif s[0] == 2:
        r = s[2]-1
        l = s[1]-1
        ans = 0
        for i in range(r-l+1):
            #print("(",f[i],d[i+l],ans,")")
            ans = (ans % 10**9 + d[i+l]% 10**9 * f[i] % 10**9)% 10**9
        print(ans) 
    elif s[0] == 3:
        r = s[2]-1
        l = s[1]-1  
        x = s[3]
        for i in range(l,r+1):
            d[i] += x


from sys import *
from math import *

mod = 1000000000
f = [0 for i in range(200)]
f[0] = f[1] = 1
for i in range(2, 200):
  f[i] = f[i - 1] + f[i - 2]
n, m = stdin.readline().split()
n = int(n)
m = int(m)
a = list(map(int, stdin.readline().split()))
for i in range(m):
  tp, x, y = stdin.readline().split()
  tp = int(tp)
  x = int(x)
  y = int(y)
  if tp == 1:
    x -= 1
    a[x] = y
  else:
    s = 0
    x -= 1
    y -= 1
    for p in range(y - x + 1):
      s += f[p] * a[x + p]
    print(s % mod)


n,m = map(int,input().split())
a = list(map(int,input().split()))

f = [1,1]
for i in range(2,n+1):
    f.append(f[i-1] + f[i-2])

for q in range(m):
    z,l,r = map(int,input().split())
    if z == 1:
        a[l-1] = r
    else:
        s = 0
        for j in range(l-1,r):
            s += (a[j] * f[j-l+1])
            s %= 10 ** 9 
        print(s)

n,m = map(int,input().split())
a = list(map(int,input().split()))

f = [1,1]
for i in range(2,n+1):
    f.append(f[i-1] + f[i-2])

for q in range(m):
    z,l,r = map(int,input().split())
    if z == 1:
        a[l-1] = r
    else:
        s = 0
        for j in range(l-1,r):
            s += (a[j] * f[j-l+1])
            s %= 10 ** 9 
        print(s)

n,m = map(int,input().split())
a = list(map(int,input().split()))

f = [1,1]
for i in range(2,n+1):
    f.append(f[i-1] + f[i-2])
    f[i] %= 10 ** 9
    
for q in range(m):
    z,l,r = map(int,input().split())
    if z == 1:
        a[l-1] = r
    else:
        s = 0
        for j in range(l-1,r):
            s += (a[j] * f[j-l+1])
            s %= 10 ** 9 
        print(s)

n,m = map(int,input().split())
a = list(map(int,input().split()))

f = [1,1]
for i in range(2,n+1):
    f.append(f[i-1] + f[i-2])
    f[i] %= 10 ** 9
    
for q in range(m):
    z,l,r = map(int,input().split())
    if z == 1:
        a[l-1] = r
    else:
        s = 0
        for j in range(l-1,r):
            s += (a[j] * f[j-l+1])
            s %= 10 ** 9 
        print(s)

n,m = list(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 = list(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)


mod = 10**9
FibArray = [1,1] 
def fibonacci(n):  
    if n<=len(FibArray): 
        return FibArray[n-1]
    else: 
        temp_fib = fibonacci(n-1)+fibonacci(n-2) 
        FibArray.append(temp_fib) 
        return temp_fib

n, m = list(map(int, input().split()))
a = list(map(int, input().split()))

for _ in range(m):
	query = list(map(int, input().split()))
	if query[0]==1:
		a[query[1]-1] = query[2]
	elif query[0]==3:
		d = query[3]
		for i in range(query[1]-1, query[2]):
			a[i]+=d
	else:
		l, r = query[1], query[2]
		s = 0
		for x in range(r-l+1):
			# print(fibonacci(x+1), a[l+x-1])
			s+=((fibonacci(x+1)*a[l+x-1]))	
		print(s%mod)