20177번 - Stock Analysis 다국어

문제

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 {(S₁, E₁, U₁ ),… , (S_m, E_m, U_m)}, write a program to find the largest sum of contiguous fluctuation values that is less than or equal to U_i in the period [S_i, E_i]for each query (S_i, E_i, U_i).

입력

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, S_i, E_i, and U_i, where [S_i, E_i] is the period from S_i to E_i over which the fluctuation values should be considered and U_i is the value that the contiguous sum should not exceed. Note that all fluctuation values are between −10⁹ and 10⁹ , 1 ≤ S_i ≤ E_i ≤ n and −10¹⁴ ≤ U_i ≤ 10¹⁴ 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 U_i and in the period [S_i, E_i] 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.

제한

힌트