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₁, a₂, ..., 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 $\text{[math]}$ , where f₀ = f₁ = 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⁵) — the number of integers in the sequence and the number of operations, correspondingly. The second line contains n integers a₁, a₂, ..., a_n (0 ≤ a_i ≤ 10⁵). 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⁵);
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⁵).

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⁹).

Summer Homework

Examples