Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

C. DZY Loves Fibonacci Numbers

time limit per test

4 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputIn mathematical terms, the sequence *F*_{n} of Fibonacci numbers is defined by the recurrence relation

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*a*_{i}, 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.

Examples

Input

4 4

1 2 3 4

1 1 4

2 1 4

1 2 4

2 1 3

Output

17

12

Note

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.

Codeforces (c) Copyright 2010-2017 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Apr/28/2017 17:17:54 (c4).

Desktop version, switch to mobile version.
User lists

Name |
---|