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

输入 #1

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

输出 #1

17
12

说明/提示

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

$1\le a_i\le 10^9$