题目描述
小批有一个整数数组 $A_1,A_2,\ldots,A_N$. 小批想当一名理论计算机科学家，所以他会在 $O((N+Q)\alpha(N))$ 的时间里在线完成 $Q$ 次对区间 $[l,r]$ 的最大子段和查询。
小嗨对小批的水平不服，但又卡不掉小批的程序。愤怒的小嗨每次会将一个值域的区间 $[L,R]$ 外的数改成 0.
小批还能在 $O((N+Q)\alpha(N))$ 时间内完成这样的查询吗？虽然小批会在线做法，但是你不一定会，所以本题允许离线。
输入格式
第一行两个整数 $N,Q$.
第二行 $N$ 个整数，第 $i$ 个表示 $A_i$.
下面 $Q$ 行，每行四个整数 $l,r,L,R$，表示将满足 $A_i \not \in [L,R]$ 的 $A_i$ 改为 0 后，$A_l,A_{l+1},\ldots,A_r$ 的最大子段和。子段可以为空。询问对序列没有影响。保证 $1 \le l \le r \le n,-10^9 \le L \le R \le 10^9$.
输出格式
$Q$ 行，每行一个整数表示对应询问的答案。
样例输入
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
样例输出
0
0
0
9
5
数据范围
对所有数据,保证 $1 ≤ N, Q ≤ 10^5 , −10^9 ≤ A_i ≤ 10^9$ .
$N, Q ≤ 5000$ ( 6 分)
$L = −10^9 , R = 10^9$ ( 13 分)
$N ≤ 20000$ ( 24 分)
$N, Q ≤ 50000$ ( 15 分)
$N, Q ≤ 75000$ ( 15 分)
没有特殊性质( 27 分)
