c. dzy loves fibonacci numbers
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
in mathematical terms, the sequence fn of fibonacci numbers is defined by the recurrence relation
f1?=?1; f2?=?1; fn?=?fn?-?1?+?fn?-?2 (n?>?2). dzy loves fibonacci numbers very much. today dzy gives you an array consisting of n integers: a1,?a2,?...,?an. moreover, there are mqueries, each query has one of the two types:
format of the query 1 l r. in reply to the query, you need to add fi?-?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 (109?+?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 a1,?a2,?...,?an (1?≤?ai?≤?109) ? 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.
sample test(s)
input
4 41 2 3 41 1 42 1 41 2 42 1 3
output
1712
题意：支持两种操作，1 l r 将 ai 加上第i-l+1项fibonacci数，l
思路：根据fibonacci数列的性质，只要知道前两项，那么可以o（1）得到后面任意项的fibonacci数以及任意前多少项的和，可以用线段树维护每个线段的和以及每段的前两
个fibonacci数，延迟更新的是每个线段的前两个fibonacci数（直接累加）