题目描述

$\red{DJL}$为了避免成为一只咸鱼，来找$\red{czgj}$学习$\red{Fibonacci}$数列。 通过$\red{czgj}$的谆谆教导，$\red{DJL}$明白了$\red{Fibonacci}$数列是这样定义的：

$\red{F(1)=1}$;$\red{F(2)=1}$;$\red{F(n)=F(n-1)+F(n-2)(n>2)}$

$\red{Czgj}$深谙熟能生巧的道理，于是他给了$\red{DJL}$一个数列，并安排了如下的训练计划：

$\red{1}$、"$\red{1 L r}$"，表示给$\red{ai }$加上$\red{F(i-L+1) ，}$其中$\red{L<=i<=r }$；

$\red{2}$、"$\red{2 L r}$"，表示询问$\red{\sum^{r}_{i=l}{a_i~modulo~1000000009(10^9+9)}}$的值。

$\red{DJL}$经过长时间的学习，感觉身体被掏空，他希望你能帮他解决这个问题。

输入格式

第一行两个整数$\red{n}$和$\red{m，}$表示原始数列的长度，和总的训练次数。

第二行$\red{n}$个整数$\red{a1,a2,...,an(1<=ai<=10^9) ，}$表示$\red{czgj}$给$\red{DJL}$的原始数列。

接下来$\red{m}$行，每一行给出三个整数，表示问题描述中的两种训练的一种。

保证$\red{1<=L<=r<=n }$。

输出格式

对于每一种形如"$\red{2 L r}$"的训练，输出一行一个整数值。

样例

输入样例

4 4
1 2 3 4
1 1 4
2 1 4
1 2 4
2 1 3

输出样例

17
12

提示

样例解释

经过第一次操作，数列变为$\red{a=[2,3,5,7] }$；

第二次询问，$\red{sum=2+3+5+7=17 }$；

经过第三次操作，数列变为$\red{a=[2,4,6,9] }$；

第四次询问，$\red{sum=2+4+6=12 }$。

数据范围

对于$\red{20\%}$的数据，$\red{1≤}$$\red{n, m≤}$$\red{100}$；

对于$\red{40\%}$的数据，$\red{1≤}$$\red{n, m≤}$$\red{1000}$；

对于$\red{100\%}$的数据，$\red{1≤}$$\red{n, m≤}$$\red{100000}$。

有关题目的提示

在阅读本段提示以前，请注意，以下给出的提示不一定是解题所必须的，也就是说，如果你跳过本段提示，也可以解决这个问题.解决问题也不一定要使用全部的提示。

特征方程:对于形如$\red{Fn=p}$·$\red{F_{n-1}+q}$·$\red{F_{n-2}}$的递推数列，令$\red{x^2=px+q，}$若该方程有两个不同的实数根$\red{x_1}$和$\red{x_2，}$则$\red{F}$的通项公式一定可以表示成$\red{F=a·}$$\red{xn+B}$·$\red{xn}$的形式，将前两项$\red{F_1}$和$\red{F_2,}$代入即可得到α和β的值。

例如求解$\red{F_1=5,F_2=15,F_n=3F_{n-1}+4F_{n-2}}$通项公式，令$\red{x^2=3x+4，}$解得$\red{x_1=4,x_2=-1，}$代入$\red{F_1}$和$\red{F_2，}$解得$\red{α=1，}$$\red{β=-1，}$则$\red{F_n= 4^n-(-1)^n}$。

二次剩余:若$\red{gcd(a,m) =1，}$且$\red{x^2=}$$\red{a(mod m)，}$则称$\red{a}$为模$\red{m }$的二次剩余。

等比数列的前$\red{n}$项和:对于等比数列$\red{an=a1}$·$\red{p^{n-1}，}$公式错误改 $\red{s_n=\begin{cases}n\times a_1~~~~(p=1)\\\frac{(1-p^n)a_1}{1-p}~~(p≠1)\end{cases}}$

$\red{Fibonacci }$数列的一个性质:若$\red{H_1=a,H_2=b,H_n=H_{n-2}+H_{n-1}，}$则$\red{H_n=a}$·$\red{F_{n-2}+b}$·$\red{F_{n-1}}$其中$\red{F}$的定义见问题描述 。