SY 公司想要分析股票。波动值（即连续两天股票价格的差值）是股票时间序列分析中最常用的数据。利用连续波动值的最大和非常重要。然而，将最大连续和作为关键指标可能存在风险。作为替代方案，公司利用在指定周期 $[S, E]$ 内不超过预定值 $U$ 的最大连续和。公司希望尽可能快地处理此类查询，其中查询定义为预定值 $U$ 和周期 $[S, E]$。

给定某只股票的 $n$ 个近期波动值和 $m$ 个查询 $\{(S_1, E_1, U_1), \dots, (S_m, E_m, U_m)\}$，请编写一个程序，为每个查询 $(S_i, E_i, U_i)$ 找出在周期 $[S_i, E_i]$ 内小于或等于 $U_i$ 的最大连续波动值之和。

输入格式

程序应从标准输入读取数据。输入的第一行包含两个整数 $n$ 和 $m$，分别表示波动值的数量和查询的数量，其中 $1 \le n \le 2,000$ 且 $1 \le m \le 200,000$。下一行包含 $n$ 个整数，表示按时间顺序从 $1$ 到 $n$ 编号的 $n$ 个波动值。接下来的 $m$ 行，每行代表一个查询，包含三个整数 $S_i, E_i$ 和 $U_i$，其中 $[S_i, E_i]$ 是应考虑波动值的周期，而 $U_i$ 是连续和不应超过的值。注意，所有波动值都在 $-10^9$ 和 $10^9$ 之间，$1 \le S_i \le E_i \le n$，且对于 $i = 1, \dots, m$，有 $-10^{14} \le U_i \le 10^{14}$。

输出格式

程序应写入标准输出。输出共 $m$ 行。第 $i$ 行应包含第 $i$ 个查询在周期 $[S_i, E_i]$ 内不超过 $U_i$ 的最大连续波动值之和。注意，每个连续和都是一个或多个连续波动值的和。当无法找到这样的和时，程序应输出 NONE。

样例

样例输入 1

5 3
1 -2 -3 5 4
1 3 -2
1 5 8
1 5 3

样例输出 1

-2
6
2

样例输入 2

6 4
3 8 -3 2 5 2
1 6 17
1 6 16
2 5 4
2 5 -4

样例输出 2

17
15
4
NONE