name

DZY Loves Fibonacci Numbers

discription

time limit per test:4 seconds
memory limit per test:256 megabytes
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:

Format of the query “1 l r”. In reply to the query, you need to add \$F_{i - l + 1}\$ to each element ai, where l ≤ i ≤ r.
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.

input

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.

output

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

hint

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.