### 问题描述 龙骑士军团是蓝桥王国战斗力最强的军团，该军团总共有 $n$ 位龙骑士，其中第 $i$ 位龙骑士的战斗力为 $a_i$。 国王想考察一下军团长小蓝对于军团的掌控能力。具体来说，国王会提出 $q$ 个询问，每次询问给定四个整数 $a, b, c, d$，并要求小蓝从区间 $[a, b]$ 中选择一个点 $L$，从区间 $[c, d]$ 中选择一个点 $R$，使得 $\sum_{i=L}^R a_i$ 的值最大化。 这些问题难倒了小蓝。作为小蓝的助手，请你帮他解决这些问题。针对每个询问，你无需找出具体的 $L$ 和 $R$，只需给出 $\sum_{i=L}^R a_i$ 的最大值即可。 ### 输入格式 第一行输入两个整数 $n,q(1 \leq n,q \leq 2 \times 10^5)$，表示龙骑士数量和国王的询问数量。 第二行输入 $n$ 个整数 $a_1,a_2,a_3,\cdots,a_n(-10^9 \leq a_i \leq 10^9)$，依稀表示每位龙骑士的战斗力。 接下来 $q$ 行，每行四个整数 $a,b,c,d(1 \leq a\leq b < c \le d \leq n)$，表示一次询问。 ### 输出格式 输出 $q$ 行，每行一个整数表示答案。 ### 样例输入 ```text 8 3 -1 2 -3 4 -5 6 -7 8 1 2 3 4 1 1 2 2 1 3 5 8 ``` ### 样例输出 ```text 3 1 5 ``` ### 样例说明 对于第一个查询，$L$ 我们可以选择 $2$，$R$ 选择 $4$，区间 $[2,4]$ 的和为 $3$。