E2. Summer Homeworktime limit per test3 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputBy 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:  For given numbers xi and vi assign value vi to element axi.  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.  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.InputThe 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. OutputFor each query print the calculated sum modulo 1000000000 (109).ExamplesInput5 51 3 1 2 42 1 42 1 52 2 41 3 102 1 5Output1232850Input5 41 3 1 2 43 1 4 12 2 41 2 102 1 5Output1245
Input5 51 3 1 2 42 1 42 1 52 2 41 3 102 1 5
Output1232850
['data structures', 'math', '*2300']