Codeforces Round #FF (Div. 2)E (line segment tree segment update)_html/css_WEB-ITnose

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:

1. 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.
2. 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数（直接累加）