题目描述

维护一个序列支持：

• 区间加
• 区间取 max
• 区间开方
• 区间查询和

输入格式

第一行两个正整数 $n,q$。

第二行 $n$ 个整数 $a_1\sim a_n$。保证 $1\le a_i\le 10^8$。

接下来 $q$ 行每行四个整数 $t,l,r,x$。

• 若 $t=1$，则表示给 $[l,r]$ 加上 $x$。保证 $0\le x\le 10^8$。
• 若 $t=2$，则表示让 $[l,r]$ 对 $x$ 取 max。保证 $1\le x\le 10^{13}$。
• 若 $t=3$，则表示给 $[l,r]$ 开方。$x$ 没用。保证 $0\le x\le 10^8$。
• 若 $t=4$，则表示给 $[l,r]$ 求和。$x$ 没用。保证 $0\le x\le 10^8$。

输出格式

对每个求和操作输出答案。

样例

输入

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

输出

3
18

数据范围

$1\le n,q\le 10^5$。