用数学术语来说,斐波那契数列 Fn 由递推关系定义
F1 = 1; F2=1; Fn = Fn - 1 + Fn - 2 (n > 2)。
DZY 非常喜欢斐波那契数列。今天 DZY 给你一个由 n 个整数组成的数组:a1, a2, ..., an。而且,有m个查询,每个查询都有以下两种类型之一:
1. 查询“1 l r”的格式。在回复查询时,需要将 Fi - l + 1 添加到每个元素 ai,其中 l ≤ i ≤ r。
2. 查询“2 l r”的格式。在回复查询时,您应该输出 $$\sum_{i=l}^{n}a_i$$ 模 1000000009 (109 + 9) 的值。
帮助DZY回复所有疑问。
输入
输入的第一行包含两个整数 n 和 m (1 ≤ n, m ≤ 300000)。第二行包含 n 个整数 a1, a2, ..., an (1 ≤ ai ≤ 109) — 初始数组 a。
然后,接下来是 m 行。单行以语句中给出的格式描述单个查询。保证对于每个查询不等式 1 ≤ l ≤ r ≤ n 成立。
输出
对于第二种类型的每个查询,在单行上打印总和的值。
示例
输入 #1
4 4 1 2 3 4 1 1 4 2 1 4 1 2 4 2 1 3
输出 #1
17 12
注意
第一次查询后,a = [2,3,5,7]。
对于第二个查询,sum = 2 + 3 + 5 + 7 = 17。
第三次查询后,a = [2,4,6,9]。
对于第四个查询,sum = 2 + 4 + 6 = 12。