You have an array of length \(N\) containing only integers between \(-10^9\) and \(10^9\) inclusive. You wonder what the maximum sum subarray is that intersects some subarray. In fact, you have \(Q\) subarrays you wish to find answers for. To help, you have decided to write a program.

Note that a subarray is a series of directly consecutive elements in an array. The sum of a subarray is the sum of the elements it comprises. Also, two subarrays intersect if and only if they share any elements (by index, not by value).

For example, say your array is \(\{-8,2,4,-1,2,-19\}\), and you wish the find the maximum sum subarray that intersects the subarray between indexes 1 and 3 (1 indexed), the answer is the subarray containing all but the first and last elements, which has sum 7.

Input Specification

The first line will contain two numbers \(N\) and \(Q\). The number of elements in your array, and the number of queries you wish to have answered about subarrays. The next line contains \(N\) space separated integers which are the elements of your array. Following this will be \(Q\) lines each each with two space separated integers \(l\) and \(r\). These are the inclusive left and right bounds of a query subarray. It is the case that \(1\leq l \leq r \leq N\), as these are 1 indexed.

Output Specification

For each query, output a single line containing a single integer. The sum of the maximum sum subarray the intersects the corresponding query subarray.

Bounds

Note this problem includes three sub-problems of increasing difficulty worth different numbers of points:

• 20 points: \(1 \leq N,Q \leq 50\)
• 20 points: \(1 \leq N,Q \leq 5000\)
• 60 points: \(1 \leq N,Q \leq 100000\)

Sample Input

5 2
3 -5 6 -9 -1
1 2
5 5

Sample Output

4
-1