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:
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 \ge 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 \le x \le ri).
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 \le n,m \le 2 \cdot 105) - the number of integers in the sequence and the number of operations, correspondingly. The second line contains n integers a1,a2,...,an (0 \le ai \le 105). Then follow m lines, each describes an operation. Each line starts with an integer ti (1 \le ti \le 3) - the operation type:
if ti=1, then next follow two integers xi vi (1 \le xi \le n,0 \le vi \le 105); if ti=2, then next follow two integers li ri (1 \le li \le ri \le n); if ti=3, then next follow three integers li ri di (1 \le li \le ri \le n,0 \le di \le 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.

For each query print the calculated sum modulo 1000000000 (109).