$Fib$ 数列为 $1,1,2,3,5,8, \ldots$，满足 $f_i=f_{i-1}+f_{i-2}$，$f_1=f_2=1$。
给定一个长度为 $n$ 的数列 $a$，你需要对其执行 $m$ 次操作，格式如下：
 $1\ l\ r$ 表示给 $a_i$ 加上 $f_{i-l+1}$，其中 $l \leq i \leq r$；
 $2\ l\ r$ 表示询问 $\sum_{i=l}^r a_i$ 的值。

现在你需要实现上述操作，并给出所有询问的答案。

第一行两个整数 $n$ 和 $m$，表示数列 $a$ 的长度和总的操作次数。
第二行 $n$ 个整数，表示数列 $a$。
接下来 $m$ 行，每一行给出三个整数，表示两种操作中的一种，保证 $1 \leq l \leq r \leq n$。

对于每个 $2$ 操作，输出一行一个整数表示答案。

4 4
1 2 3 4
1 1 4
2 1 4
1 2 4
2 1 3

17
12