题目描述

在本题中，我们用 $f_i$ 来表示第 $i$ 个斐波那契数（$f_1=f_2=1,\ f_i=f_{i-1}+f_{i-2},\ (i≥3)$）。

维护一个序列 $a$，长度为 $n$，有 $m$ 次操作：

• 1 l r：对于 $l≤i≤r$，将 $a_i$ 加上 $f_{i-l+1}$。
• 2 l r：求 $(∑_{i=l}^r a_i)\mod\ (10^9+9)$。

输入格式

第一行两个整数 $n,m$，$1\le n,m\le 3\times 10^5$。

第二行 $n$ 个整数 $a_i$，$1\le a_i\le 10^9$。

接下来 $m$ 行，每行一个操作。

输出格式

对于每个操作 $2$，在一行中输出一个整数表示答案。

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

17
12