human
Can you provide a Python program to print the calculated sum modulo 1000000000 (109) given the following:
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 , 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
The above is tricky. Write me a correct solution in PYTHON3.
assistant
#Here is Python program to print the calculated sum modulo 1000000000 (109).

# import itertools
# import bisect
# import math
from collections import defaultdict, Counter
import os
import sys
from io import BytesIO, IOBase

# sys.setrecursionlimit(10 ** 5)
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():
    # for _ in " " * int(input()):
    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
    ...