Migrated from Lutece 2384 我，不是说了能力要平均值么 · 改二

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

转生异世界时，栗原海里请求神赐予她平均值的能力，导演组故意找了一个不会计算平均数的神，神很自然地给出了最大值与最小值和的一半的结果——在数学上这显然是错误的，但是剧情就变得很有意思了。

形式化地，若有一由 $n$ 个数组成的有限数列 $\{x_n\}$，则这列数的平均值应为 $\bar x=\frac{1}{n}\sum_{i=1}^n x_i$，并定义斐波那契数列 $\{f_n\}$，$f_1=f_2=1$，对于 $i\ge 3$，$f_i=f_{i-1}+f_{i-2}$。栗源海里显然知道平均数应该怎么计算，于是她在思考如果利用真正的平均值定义的话情况会是怎样的。

现在异世界有 $n$ 个生物，编号为 $1\ldots n$。神会随机选择一个区间 $[l,r]\ (l\le r\le n,l,r\in \mathbb{N}_+)$，并取编号在区间内的所有生物的能力平均值作为栗原海里的能力值。根据辩证唯物主义，物质是运动的，所以这些生物的能力也是在变化的。总的来说，按时间顺序会发生如下两类事件：

• 知道了神选择的区间，如果在这一时刻神要分配能力，栗原海里想知道她的能力值是多少；
• 编号在区间 $[l,r]$ 范围内的生物能力值增长了，对于区间内编号为 $i$ 的生物，能力增长了 $f_{i-l+x}^2$。

请输出能力值对 $10^9+9$ 取模后的值。

Input

第一行两个数 $n,m$，分别表示生物数和总事件数；

接下来一行 $n$ 个数 $a_i$，表示编号为 $i$ 的生物的初始能力值；

接下来 $m$ 行，每行表示一个事件，你需要按输入顺序处理：

• $\texttt{1 l r}$：表示神选择了 $[l,r]$ 区间，你需要按照真实的平均值定义输出这段区间的平均值；
• $\texttt{2 l r x}$：表示区间 $[l,r]$ 内的生物能力值增长了。

Output

对于每次询问，输出一个整数，代表所求平均值对 $10^9+9$ 取模后的值。

对于一个表示成 $\frac{p}{q}$ 的有理数（其中 $p\in \mathbb{N},q\in \mathbb{N}_+$，且 $\gcd(p,q)=1$），请输出 $p\times q^{-1}$ 对 $10^9+9$ 取模后的值，其中 $q^{-1}$ 表示 $q$ 在模 $10^9+9$ 意义下的逆元。

Samples

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

3
7

Constraints

$1\le n,m\le 2\times 10^5,0\le a_i\lt 10^9+9,1\le l\le r\le n,1\le x\le 10^9$

Note

对于第一个事件，输出 $\{1,2,3,4,5\}$ 的平均值对 $10^9+9$ 取模后的值，为 $3$；

对于第二个事件，这 $n$ 个生物的能力值变为 $\{1,2,4,8,14\}$；

对于第三个事件，输出 $\{2,4,8,14\}$ 的平均值对 $10^9+9$ 取模后的值，为 $7$。

若 $\exists t\in[1,P),t\in \mathbb{N}_+$，满足 $at\equiv 1\pmod P$，则称 $t$ 为 $a$ 在模 $P$ 意义下的逆元。记作 $a^{-1}$。

逆元的求解并不是本题的考点，可以查阅资料自行学习。

Resources

2020 UESTC ICPC Training for Data Structures