시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 195 33 27 22.881%

문제

SY Company wants to analyze a stock. The fluctuation value, which is the difference in stock prices for two consecutive days, is the most frequently used data for the time-series analysis of the stock. It is important to utilize the largest sum of the contiguous fluctuation values. However, using the largest contiguous sum as a key indicator could be risky. As an alternative, the company utilizes the largest contiguous sum that is not greater than a predetermined value U in a specified period [S, E] from S to E. The company wants to process such queries as fast as possible, where a query is defined as a predetermined value U and a period [S, E].

Given a collection of n recent fluctuation values for some stock and m queries {(S1, E1, U1 ),… , (Sm, Em, Um)}, write a program to find the largest sum of contiguous fluctuation values that is less than or equal to Ui in the period [Si, Ei]for each query (Si, Ei, Ui).

입력

Your program is to read from standard input. The input starts with a line containing two integers, n and m, representing the number of fluctuation values and the number of queries respectively, where 1 ≤ n ≤ 2,000 and 1 ≤ m ≤ 200,000. The next line contains n integers representing n fluctuation values, which are numbered in chronological order from 1 to n. Each of the following m lines represents a query that consists of three integers, Si, Ei, and Ui, where [Si, Ei] is the period from Si to Ei over which the fluctuation values should be considered and Ui is the value that the contiguous sum should not exceed. Note that all fluctuation values are between −109 and 109 , 1 ≤ SiEin and −1014Ui ≤ 1014 for i = 1, … , m.

출력

Your program is to write to standard output. Print exactly m lines. The i-th line should contain the largest sum of contiguous fluctuation values that does not exceed Ui and in the period [Si, Ei] for the i-th query. Note that every contiguous sum is the sum of one or more consecutive fluctuation values. When it is impossible to find such the sum, the program should print 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