CF446C DZY Loves Fibonacci Numbers

斐波那契数列 $f_n$ 由以下递推式定义： - $f_1=f_2=1$ - $f_n=f_{n-1}+f_{n-2}\;(n>2)$ DZY 很喜欢斐波那契数列，它给了你 $n$ 个整数 $a_1,a_2,\cdots,a_n$. 你需要执行 $m$ 个操作，操作分两种： - `1 l r`：对所有 $l\le i\le r$，将 $a_i$ 加上 $f_{i-l+1}$. - `2 l r`：求 $a_l\sim a_r$ 的和，对 $10^9+9$ 取模.

第一行两个整数 $n,m$. 第二行 $n$ 个整数 $a_1,a_2,\cdots,a_n$. 接下来 $m$ 行，每行三个整数表示一个操作.

对每个 $2$ 操作，一行一个整数表示答案.

$1\le n,m\le 3\times 10^5$ $1\le a_i\le 10^9$