[SNOI2020] 区间和

有一个长度为 $n$ 的整数数列 $a_1,a_2,\cdots,a_n$（可能含有负数）。现在对其进行 $q$ 次操作，每次操作是以下二者之一： - `0 l r x` 表示对于 $[l,r]$，将 $a_i$ 赋值为 $\max(a_i,x)$； - `1 l r` 求区间 $[l,r]$ 的最大子段和。即：$\max(0, \max_{l\le u\le v\le r} (\sum_{i=u}^v a_i))$。

第一行两个正整数 $n,q$，分别表示序列长度和操作次数； 第二行 $n$ 个正整数 $a_1,a_2,\cdots,a_n$ 表示初始的序列； 接下来 $q$ 行，每行形如 `0 l r x` 或 `1 l r` 表示一次操作。

对于每个形如 `1 l r` 的操作，输出一行一个整数表示答案。

5 7
2 -4 6 -5 5
1 1 5
0 1 5 -4
1 1 5
0 3 4 -1
1 1 5
0 1 3 -1
1 1 5

6
7
10
11

#### 样例说明 对于样例 $1$： - 第 $1$ 次询问时序列为 $2,-4,6,-5,5$，最大子段和为 $6$； - 第 $2$ 次询问时序列为 $2,-4,6,-4,5$，最大子段和为 $7$； - 第 $3$ 次询问时序列为 $2,-4,6,-1,5$，最大子段和为 $10$； - 第 $4$ 次询问时序列为 $2,-1,6,-1,5$，最大子段和为 $11$。 #### 数据规模与约定 对于所有数据，$1\le n\le10^5, 1\le q\le 2\times 10^5, |a_i|, |x|\le 10^9$。 - 对于 $10\%$ 的数据，$n,q \le 200$； - 对于另外 $10\%$ 的数据，$n,q \le 2000$； - 对于另外 $25\%$ 的数据，每次操作 $0$ 均满足 $l=r$（即，只有单点修改）； - 对于另外 $20\%$ 的数据，每次操作 $1$ 均满足 $l=1,r=n$（即，只有全局询问）； - 对于余下 $35\%$ 的数据，无特殊限制。 **有来自出题人的 3 个 hack 数据点**