Migrated from Lutece 3118 The Happy Prince and Other Tales

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

Tag：二维线段树/二维树状数组

I dwell in Possibility — 我居于可能性之中—

A fairer House than Prose — 一座比散文更为华美的屋宇—

More numerous of Windows — 更为众多的窗户—

Superior — for Doors — 其超卓之处—是为门—

Of Chambers as the Cedars — 有内室密如雪松林—

Impregnable of Eye — 当为肉眼难以看得清—

And for an Everlasting Roof 以为其永恒的屋顶

The Gambrels of the Sky — 则有天空错落有致的复折—

Of Visitors — the fairest — 有来宾—最精雅—

For Occupation — This — 为定居—亦无他—

The spreading wide of narrow Hands 唯需尽情伸展我纤巧的双手

To gather Paradise — 把天国尽收拢—

樱之艺术家（草薙直哉）正在面对强大的美神（御樱稟）给他设下的挑战。

在直哉的面前共排布着 $n$ 幅风格迥异的画，其中第 $i$ 幅画有一个美丽度，用整数 $a_i$ 来表示（注意美丽度可能是负值）。

定义一段区间 $[l,r]$ 的美丽值为其中包含的所有画的美丽度之和，即 $\sum_{i=l}^r a_i$ 。

现在稟为直哉准备了 $m$ 个问题，每个问题可以由一个三元组 $(S_i,E_i,U_i)$ 来描述。

对于每个问题，直哉需要找到区间 $[S_i,E_i]$ 中的一个子区间，使得这段区间的美丽值小于等于 $U_i$ ，且这段区间的美丽值最大。

形式化地，对于每次询问 $(S_i,E_i,U_i)$ ，你需要找到区间 $[l,r]$ （ $S_i\le l\le r\le E_i$ ），满足 $\sum_{j=l}^r a_j\le U_i$ ，在此基础上最大化 $\sum_{j=l}^r a_j$ 的值。

Input

输入的第一行包括两个正整数 $n,m$ ，分别表示需要画作的数量以及问题的数量。

第二行包括一个长为 $n$ 的序列 $\{a_n\}$ ，其中 $a_i$ 为第 $i$ 幅画的美丽度。

接下来的 $m$ 行每行三个整数 $S_i,E_i,U_i$ ，意义如上所述。

Output

输出共包括 $m$ 行，每行一个整数，表示直哉对稟的每个问题的答案。

如果找不到任何一个区间满足要求，输出NONE以代替。

Samples

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

-2
6
2

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

17
15
4
NONE

Constraints

$1\le n\le 2000,1\le m\le 2\times 10^5,-10^9\le a_i\le 10^9,1\le S_i\le E_i\le n,-10^{14}\le U_i\le 10^{14}$

Resources

2024 UESTC ICPC Training for Data Structures