时间限制：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\ v\)：把 \(a[i],a[i+1],...,a[j]\) 都修改成 \(v（|v|≤100）\)。
　　\(3\ i\ j\)：输出 \(max(a[i],a[i+1],...a[j]) * (a[i]+a[i+1]+...+a[j])\) 的值。

【输入格式】

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

【输出格式】

　　输出操作3的结果。

【输入输出样例】

　Input

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

　Output

240
105
8

【数据限制】

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

【来源】

　　Mr.he