给定一个长度为 $N$ 的序列 $A_1, A_2, \ldots, A_N$。请编写程序执行以下查询：

• 0 l r x：对于所有 $l \le i \le r$，将 $A_i$ 赋值为 $\max(A_i, x)$。
• 1 l r：输出 $\max\left(0, \max_{l \le u \le v \le r} \left(\sum_{i=u}^{v} A_i\right)\right)$。

输入格式

第一行包含两个整数 $N$ 和 $Q$，分别表示序列的长度和查询的数量。

第二行包含 $N$ 个整数 $A_1, A_2, \ldots, A_N$，表示序列 $A$ 的初始元素。

接下来 $Q$ 行，每行描述一个查询，格式如上所述。

输出格式

对于每个 1 l r 形式的查询，输出一行答案。

样例

输入格式 1

14 14
-3 2 1 -2 3 -4 3 -5 -1 -2 3 -5 1 5
1 3 9
0 1 14 -4
1 1 14
0 3 11 -1
1 2 8
0 3 10 -1
1 4 7
0 6 9 2
1 1 14
0 10 10 7
1 1 14
0 6 9 4
0 1 5 2
1 1 14

输出格式 1

3
6
7
5
18
26
39