时间限制：0.5秒　　内存限制：256M

---

【题目描述】

　　给出一个有 \(n\) 个元素的的数组：\(a[1],a[2],...,a[n]（|a[i]|≤100）\)，你的任务是设计一个数据结构，支持以下两种操作：
　　\(1\ i\ j\ v\)：把 \(a[i],a[i+1],...,a[j]\) 都增加 \(v（|v|≤100）\)。
　　\(2\ i\ j\)：输出 \(max(a[i],a[i+1],...a[j]) * (a[i]+a[i+1]+...+a[j])\) 的值。

【输入格式】

　　第一行包含两个正整数：\(n\) 和 \(m\) 。第二行为 \(n\) 整数，表示 \(a[i]\)。再以下 \(m\) 行，每行为上述两种操作之一。

【输出格式】

　　输出操作2的结果。

【输入输出样例】

　Input

10 7
1 2 3 4 5 6 7 8 9 10
2 4 8
1 3 7 2
1 4 8 5
2 3 7
1 6 9 -2
1 3 5 -5
2 4 7

　Output

240
770
432

【数据限制】

　　对于 \(100\%\) 的数据，\(1≤n,m≤200000\)。

【来源】

　　Mr.he