No tag edit access

E2. Summer Homework

time limit per test

3 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard 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 *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*_{xi}. - For given numbers
*l*_{i}and*r*_{i}you've got to calculate sum , 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

Codeforces (c) Copyright 2010-2017 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Aug/21/2017 15:02:35 (c3).

Desktop version, switch to mobile version.

User lists

Name |
---|