Yaroslav has n points that lie on the $Ox$ axis. The coordinate of the first point is $x_1$, the coordinate of the second point is $x_2$, ..., the coordinate of the n-th point is — $x_n$. Now Yaroslav wants to execute $m$ queries, each of them is of one of the two following types:
In mathematical terms, the sequence $F_n$ of Fibonacci numbers is defined by the recurrence relation
$$F_1 = 1; F_2 = 1; F_n = F_{n - 1} + F_{n - 2} (n > 2)$$
DZY loves Fibonacci numbers very much. Today DZY gives you an array consisting of n integers: $a_1, a_2, \dots, a_n$. Moreover, there are $m$ queries, each query has one of the two types: