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.