주가 분석

SY Company는 주가를 분석하려고 한다. 연속한 두 날의 주가 차이인 변동값은 주가 시계열 분석에서 가장 많이 쓰이는 데이터이다. 변동값의 연속 구간 합 중 가장 큰 값을 활용하는 것이 중요하다. 그러나 가장 큰 연속 구간 합을 핵심 지표로 사용하는 것은 위험할 수 있다. 대신 회사는 특정 기간 [S, E]에서 미리 정한 값 U보다 크지 않은 연속 구간 합 중 가장 큰 값을 활용한다. 회사는 이러한 질의를 최대한 빠르게 처리하려고 하며, 질의는 미리 정한 값 U와 기간 [S, E]로 정의된다.

어떤 주식의 최근 변동값 n개와 m개의 질의 {(S1, E1, U1 ),… , (Sm, Em, Um)}가 주어질 때, 각 질의 (Si, Ei, Ui)에 대해 기간 [Si, Ei]에서 Ui 이하인 연속 구간 합 중 가장 큰 값을 구하는 프로그램을 작성하라.

프로그램은 표준 입력에서 입력을 읽는다. 입력의 첫 줄에는 변동값의 개수와 질의의 개수를 나타내는 두 정수 n과 m이 주어지며, 1 ≤ n ≤ 2,000이고 1 ≤ m ≤ 200,000이다. 다음 줄에는 n개의 변동값을 나타내는 n개의 정수가 주어지며, 이 값들은 시간 순서대로 1부터 n까지 번호가 붙는다. 이어지는 m개의 줄에는 각각 질의를 나타내는 세 정수 Si, Ei, Ui가 주어지며, [Si, Ei]는 변동값을 고려할 Si부터 Ei까지의 기간이고 Ui는 연속 구간 합이 넘지 않아야 하는 값이다. 모든 변동값은 −10^9와 10^9 사이이고, 1 ≤ Si ≤ Ei ≤ n이며, i = 1, … , m에 대해 −10^14 ≤ Ui ≤ 10^14이다.

프로그램은 표준 출력에 출력을 쓴다. 정확히 m개의 줄을 출력한다. i번째 줄에는 i번째 질의에 대해 기간 [Si, Ei]에서 Ui를 넘지 않는 연속 구간 합 중 가장 큰 값을 출력한다. 모든 연속 구간 합은 하나 이상의 연속한 변동값의 합이다. 그러한 합을 찾을 수 없으면 프로그램은 NONE을 출력한다.