CF446C.DZY Loves Fibonacci Numbers

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 (109 + 9).

Help DZY reply to all the queries.

在数学上，斐波那契数列 $F_n$ 由如下递推关系定义：

$$F_1 = 1;\quad F_2 = 1;\quad F_n = F_{n-1} + F_{n-2}\quad (n > 2).$$

DZY 非常喜爱斐波那契数。今天 DZY 给你一个包含 $n$ 个整数的数组：$a_1, a_2, \dots, a_n$。此外，还有 $m$ 个查询，每个查询为以下两种类型之一：

1. 查询格式为 "1 l r"。对于该查询，你需要对每个下标 $i$（其中 $l \le i \le r$），将 $F_{i-l+1}$ 加到元素 $a_i$ 上。
2. 查询格式为 "2 l r"。对于该查询，你需要输出 $\displaystyle\sum_{i=l}^{r} a_i$ 对 $1000000009$（即 $10^9 + 9$）取模的结果。

请帮助 DZY 回答所有查询。

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

输入的第一行包含两个整数 $n$ 和 $m$（$1 ≤ n, m ≤ 300000$）。第二行包含 $n$ 个整数 $a_1, a_2, ..., a_n$（$1 ≤ a_i ≤ 10^9$）—— 初始数组 $a$。

接下来是 $m$ 行。每行描述一个查询，格式如题面所述。保证对每个查询均满足不等式 $1 ≤ l ≤ r ≤ n$。

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

对于每个第二类查询，在单独一行中输出该和的值。

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.

第一次查询后，$a = [2, 3, 5, 7]$。

第二次查询时，$\text{sum} = 2 + 3 + 5 + 7 = 17$。

第三次查询后，$a = [2, 4, 6, 9]$。

第四次查询时，$\text{sum} = 2 + 4 + 6 = 12$。