题目描述

给一个长为 $n$ 的序列，有 $m$ 次查询操作。

查询操作形如 $l\;r\;L\;R$，表示将序列中值在 $[L,R]$ 内的位置保留不变，其他的位置变成 $0$ 时，序列中 $[l,r]$ 区间内的最大子段和，这个子段可以是空的。

输入格式

第一行两个整数 $n,m$。

第二行 $n$ 个整数表示这个序列。

之后 $m$ 行，每行四个整数 $l\;r\;L\;R$ 表示一次查询操作。

输出格式

输出 $m$ 行，每行一个整数表示答案。

样例 #1

样例输入 #1

6 5
-1 1 -4 5 -1 4
1 1 4 5
1 1 4 514
2 3 3 3
1 6 -1 5
2 5 2 5

样例输出 #1

0
0
0
9
5

提示

Idea：nzhtl1477，Solution：ccz181078，Code：ccz181078，Data：nzhtl1477

对于 $100\%$ 的数据，$1\leq n,m \le 10^5$，序列中所有数的绝对值 $\le 10^9$。

第四组查询中，值域限制是 $[-1,5]$，序列为 -1 1 0 5 -1 4，区间 $[1,6]$ 的最大子段为 $[2,6]$，和为 $9$。

第五组查询中，值域限制是 $[2,5]$，序列为 0 0 0 5 0 4，区间 $[2,5]$ 的最大子段为 $[4,4]$（并列），和为 $5$。