Package for this problem was not updated by the problem writer or Codeforces administration after we’ve upgraded the judging servers. To adjust the time limit constraint, solution execution time will be multiplied by 2. For example, if your solution works for 400 ms on judging servers, then value 800 ms will be displayed and used to determine the verdict.

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

E1. 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: Nov/24/2017 19:31:15 (c4).

Desktop version, switch to mobile version.

User lists

Name |
---|