CF446C DZY Loves Fibonacci Numbers

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},...,a_{n} $ . Moreover, there are $ m $ queries, each query has one of the two types: 1. Format of the query " $ 1\ l\ r $ ". In reply to the query, you need to add $ F_{i-l+1} $ to each element $ a_{i} $ , where $ l

N/A

N/A

After the first query, $ a=[2,3,5,7] $ . For the second query, $ sum=2+3+5+7=17 $ . After the third query, $ a=[2,4,6,9] $ . For the fourth query, $ sum=2+4+6=12 $ .