DZY Loves Fibonacci Numbers

- 在本题中，我们用 $f_i$ 来表示第 $i$ 个斐波那契数（$f_1=f_2=1,f_i=f_{i-1}+f_{i-2}(i\ge 3)$）。 - 维护一个序列 $a$，长度为 $n$，有 $m$ 次操作： 1. `1 l r`：对于 $l\le i\le r$，将 $a_i$ 加上 $f_{i-l+1}$。 2. `2 l r`：求 $\displaystyle\left(\sum_{i=l}^ra_i\right)\bmod(10^9+9)$。 - $1\le n,m\le 3\times 10^5$，$1\le a_i\le 10^9$。

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<=i<=r $ . 2. Format of the query " $ 2\ l\ r $ ". In reply to the query you should output the value of  modulo $ 1000000009 (10^{9}+9) $ . Help DZY reply to all the queries.

The first line of the input contains two integers $ n $ and $ m $ ( $ 1<=n,m<=300000 $ ). The second line contains $ n $ integers $ a_{1},a_{2},...,a_{n} (1<=a_{i}<=10^{9}) $ — initial array $ a $ . Then, $ m $ lines follow. A single line describes a single query in the format given in the statement. It is guaranteed that for each query inequality $ 1<=l<=r<=n $ holds.

For each query of the second type, print the value of the sum on a single line.

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

17
12

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 $ .