I. Stock Analysis
time limit per test
2 s
memory limit per test
512 megabytes
input
standard input
output
standard output

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_1, E_1, U_1), \ldots , (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)$$$.

Input

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 \leq n \leq 2,000$$$ and $$$1 \leq m \leq 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^9$$$ and $$$10^9$$$, $$$1 \leq S_i \leq E_i \leq n$$$ and $$$−10^{14} \leq U_i \leq 10^{14}$$$ for $$$i = 1, \ldots , m$$$.

Output

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.

Examples
Input
5 3
1 -2 -3 5 4
1 3 -2
1 5 8
1 5 3
Output
-2
6
2
Input
6 4
3 8 -3 2 5 2
1 6 17
1 6 16
2 5 4
2 5 -4
Output
17
15
4
NONE