CF316E3.Summer Homework

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_1, _a_2, ..., a__n. Your task is to perform on it m consecutive operations of the following type:

1. For given numbers x__i and v__i assign value v__i to element a__x__i.
2. 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.
3. 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.

三岁的时候，聪明的海狸已经掌握了全部算术运算，今年暑假，他那惊讶不已的老师给他布置了如下作业：

给定一个整数序列 $a_1, a_2, \dots, a_n$。你需要对该序列依次执行 $m$ 个操作，操作类型如下：

1. 给定数字 $x_i$ 和 $v_i$，将元素 $a_{x_i}$ 的值赋为 $v_i$；
2. 给定数字 $l_i$ 和 $r_i$，你需要计算和式 ，其中 $f_0 = f_1 = 1$，且当 $i \ge 2$ 时，$f_i = f_{i-1} + f_{i-2}$；
3. 给定三个数字 $l_i$、$r_i$、$d_i$，对所有满足 $l_i \le x \le r_i$ 的下标 $x$，将 $a_x$ 的值增加 $d_i$。

聪明的海狸计划环游加拿大著名的湖泊，因此请你帮他解决这个问题。

The first line contains two integers n and m (1 ≤ n, m ≤ 2·105) — 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 ≤ 105). 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 ≤ 105);
• 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 ≤ 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.

第一行包含两个整数 $n$ 和 $m$（$1 \leq n, m \leq 2 \cdot 10^5$），分别表示序列中整数的个数和操作的个数。第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$0 \leq a_i \leq 10^5$）。接下来是 $m$ 行，每行描述一个操作。每行以一个整数 $t_i$（$1 \leq t_i \leq 3$）开头，表示操作类型：

• 若 $t_i = 1$，则随后是两个整数 $x_i$ 和 $v_i$（$1 \leq x_i \leq n$，$0 \leq v_i \leq 10^5$）；
• 若 $t_i = 2$，则随后是两个整数 $l_i$ 和 $r_i$（$1 \leq l_i \leq r_i \leq n$）；
• 若 $t_i = 3$，则随后是三个整数 $l_i$、$r_i$ 和 $d_i$（$1 \leq l_i \leq r_i \leq n$，$0 \leq d_i \leq 10^5$）。

得分为 30 分的输入限制（子问题 E1）：

• 保证 $n$ 不超过 100，$m$ 不超过 10000，且不包含第 3 类查询。

得分为 70 分的输入限制（子问题 E1+E2）：

• 保证只包含第 1 类和第 2 类查询。

得分为 100 分的输入限制（子问题 E1+E2+E3）：

• 无额外限制。

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

对于每个查询，输出计算得到的和对 1000000000（$10^9$）取模的结果。