题目描述与 552 相同。不同的是本题时限缩短为 $\texttt{6s}$，且仅测试六个极限数据。

序列(seq)

题目描述

Kujou Kawaii 有一个长度为 $n$ 的序列 $a$。

Kujou Kawaii 有 $Q$ 次不同的操作，操作如下：

$1\ l\ r$: 执行如下代码：

for (int i=l;i+1<=r;i++)
    if (a[i]>a[i+1])
        swap(a[i],a[i+1]);

$2\ l\ r$: 执行如下代码：

unsigned long long ans=0
for (int i=l;i<=r;i++)
    ans+=a[i];
cout<<ans<<endl;

Kujou Kawaii 迫切的想知道每一次操作二的答案。你需要帮助她解决这个问题。

输入格式

第一行两个正整数 $n$, $Q$.

第二行 $n$ 个正整数，第i个数字表示 $a_i$。

接下来 $Q$ 行，每行三个数字，表示一次操作。

输出格式

对于操作 $2$，一行一个数字表示答案。

样例

input

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

output

9
6

数据范围

对于所有测试数据，满足 $1 \le n \le 3 \times 10^5,1 \le Q \le 4 \times 10^4,0 \le a_i \le 10^9$。

时间限制：$\texttt{6s}$

空间限制：$\texttt{512MB}$