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: MEDIUM
Tags: Data structures

Complete search
Skill types: Data structures

Complete search

Starter code:

Solutions:
(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) = 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())
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):
			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


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):
			s += fibonacci(x + 1) * a[l + x - 1]
		print(s % mod)


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] * 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)


import sys
f = [-1] * 200000

def fib(n):
	if f[n] == -1:
		k = n // 2
		while k > 0 and f[k] == -1:
			k = k / 2
		for i in range(k, n):
			f[i + 1] = f[i] + f[i - 1]
	return f[n]

def solve(numbers, t, l, r, d):
	if t == 1:
		numbers[l - 1] = r
	elif t == 2:
		total = 0
		for j in range(l - 1, r):
			total = (total + numbers[j] * fib(j - l + 1)) % 10 ** 9
		print(total)
	else:
		for j in range(l - 1, r):
			numbers[j] = numbers[j] + d
(n, m) = sys.stdin.readline().rstrip().split()
n = int(n)
m = int(m)
numbers = list(map(lambda x: int(x), sys.stdin.readline().rstrip().split()))
f[0] = f[1] = 1
for i in range(m):
	line = sys.stdin.readline().rstrip().split()
	t = int(line[0])
	d = 0
	if t == 1:
		l = int(line[1])
		r = int(line[2])
	elif t == 2:
		l = int(line[1])
		r = int(line[2])
	else:
		l = int(line[1])
		r = int(line[2])
		d = int(line[3])
	solve(numbers, t, l, r, d)


from collections import defaultdict, Counter
import os
import sys
from io import BytesIO, IOBase
ii = lambda : int(input())
lmii = lambda : list(map(int, input().split()))
slmii = lambda : sorted(map(int, input().split()))
li = lambda : list(input())
mii = lambda : map(int, input().split())
msi = lambda : map(str, input().split())

def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)

def lcm(a, b):
	return a * b // gcd(a, b)

def main():
	(n, m) = mii()
	a = lmii()
	fac = [1, 1]
	for i in range(10 ** 5):
		fac.append(fac[-1] + fac[-2] % 10 ** 9)
	for i in range(m):
		lst = lmii()
		if lst[0] == 1:
			a[lst[1] - 1] = lst[2]
		elif lst[0] == 2:
			s = 0
			for j in range(lst[2] - lst[1] + 1):
				s += fac[j] * a[lst[1] - 1 + j] % 10 ** 9
			print(s % 10 ** 9)
		else:
			for j in range(lst[1], lst[2] + 1):
				a[j - 1] += lst[3]
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()