Sasha and Array
时间限制：C/C++/Rust/Pascal 5秒，其他语言10秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

在本题中，我们用 f_i 来表示第 i 个斐波那契数（）。
- 给定一个 n 个数的序列 a。有 m 次操作，操作有两种：
1. 将 加上 x。
2. 求 。

输入描述:

第一行两个正整数。
第二行n个正整数。
接下来m行，每行包含下面两种形式中的一种，含义如题面所述：
；
。

输出描述:

对于每个查询，输出答案。
示例1

输入

复制 
5 4
1 1 2 1 1
2 1 5
1 2 4 2
2 2 4
2 1 5

输出

复制 
5
7
9

说明

最初，数组a 为 1 , 1 , 2 , 1 , 1 .

第一个询问的答案为： f(1)+f(1)+f(2)+f(1)+f(1)=1+1+1+1+1=5 .

在第二次操作后，数组a 变成 1 , 3 , 4 , 3 , 1 .

第三个询问的答案为： f(3)+f(4)+f(3)=2+3+2=7 .

第四个询问的答案为： f(1)+f(3)+f(4)+f(3)+f(1)=1+2+3+2+1=9 .

备注:

原题链接：https://codeforces.com/problemset/problem/719/E