Summer Homework

Description:

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

Sample Input:

5 5
1 3 1 2 4
2 1 4
2 1 5
2 2 4
1 3 10
2 1 5

Sample Output:

12
32
8
50

Sample Input:

5 4
1 3 1 2 4
3 1 4 1
2 2 4
1 2 10
2 1 5

Sample Output:

12
45