響符「パワーレゾナンス」
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

幽谷响子最近在妖怪之山中依靠回声朗诵经文。
她事先已经朗诵过 n 篇经文，其中第 i 篇经文回声的响度为 a_i 。由于城管正在妖怪之山泡温泉，因而她计划在执行完 q 次操作后立刻离开。
响子酱的操作有以下两种：
  • 1\ l\ r ：表示响子酱根据所有满足 l \le i \le r 的经文回声响度 a_i ，再次进行朗诵，即 a_i = F(a_i) ；
  • 2\ l\ r ：表示响子酱接收所有满足 l \le i \le r 的的经文响度 a_i 后，在本子上记录下一行，一行只有一个数字，表示 \sum_{i=l}^{r} a_i ，即经文响度之和。
其中，响子再次朗诵经文的操作 F(x) 表示如下。
F(x) = 2 \bigg\lfloor \cfrac{ |x^3 - 3x| }{3 x^2 + 1} \bigg\rfloor
其中 \lfloor x \rfloor 为向下取整，即 \lfloor 1.9 \rfloor = 1, \lfloor 2 \rfloor = 2 。
在响子执行完 q 次操作以后，她在本子上记录的内容是什么呢？

输入描述:

第一行，两个正整数 n, q ，分别表示响子酱朗诵的经文数与其操作数。

第二行，给出 n 个整数，表示响子酱事先朗诵经文的响度 a_i ， i 从 1 开始。

接下来 q 行，每行给出三个正整数 opt, l, r 。

- 若 opt = 1 ，表示第一种操作，即对于区间 [l, r] 内的每个响度 x ， x = F(x) ；
- 若 opt = 2 ，表示第二种操作，即输出对于区间 [l, r] ，响度之和 \sum_{i=l}^{r} a_i 。

输出描述:

对于每一个 opt=2 的操作，输出单独一行一个数字，表示询问区间 [l, r] 经文的响度之和 \sum_{i=l}^{r} a_i 。
示例1

输入

复制 
1 3
114
2 1 1
1 1 1
2 1 1

输出

复制 
114
74
示例2

输入

复制 
5 5
114 514 1919 810 495
2 1 5
1 1 4
2 4 5
1 3 5
2 2 4

输出

复制 
3852
1033
1550

备注:

【样例解释】
对于第一个样例，其计算过程如下：

\begin{aligned}<br /><br /> F(114) &= 2 \times \bigg\lfloor \cfrac{ |114^3 - 3 \times 114| }{ 3 \times 114^2 + 1 } \bigg\rfloor \\<br /><br /> &= 2 \times \bigg\lfloor \cfrac{1481202}{38989} \bigg\rfloor \\<br /><br /> &= 2 \times 37 \\<br /><br /> &= 74<br /><br />\end{aligned}

【评测用例规模与约定】
对于 20\% 分数的数据，保证 1 \le n, q \le 10^2 。

对于 40\% 分数的数据，保证 1 \le n \le 5 \times 10^4, 1 \le q \le 10^5 。

对于 100\% 的数据，保证 1 \le n \le 10^5, 1 \le q \le 3 \times 10^5 。

对于所有的 a_i ，保证 0 \le a_i \le 10^6 。

对于所有的 opt ，保证 opt \in \{1, 2\} 。

对于所有的 l, r ，保证 1 \le l \le r \le n 。