Optimal Stone Merge

You are given (n) piles of stones, where the (i)-th pile has (a_i) stones. Initially, you choose a starting pile. Then, repeatedly, you merge the current pile with one of its adjacent piles (either the one immediately to the left or the one immediately to the right). Merging two piles with (x) and (y) stones costs (x+y) units of effort and creates a new pile consisting of (x+y) stones. Once a merge is performed, the new pile takes the place of the two merged piles. Your task is to determine, for a given range ([l, r]), the minimum total effort required to merge all (n) piles into one if you choose each pile with index in ([l, r]) as the initial starting pile.


Note: The merge operations must be performed in such a way that at every step, you merge the current (merged) pile with one of its immediate neighbors. The order in which you decide to merge (i.e. whether to extend to the left or to the right at each step) will affect the total cost. It is guaranteed that all (a_i) are random.

inputFormat

The input begins with a line containing two integers (n) and (q), denoting the number of stone piles and the number of queries, respectively.

The second line contains (n) integers (a_1, a_2, \ldots, a_n) representing the number of stones in each pile.

Each of the next (q) lines contains two integers (l) and (r). For each query, you need to consider each pile with index in ([l, r]) as the starting pile.

outputFormat

For each query, output (r-l+1) integers separated by a space. The (i)-th number (with (1 \le i \le r-l+1)) represents the minimum total effort required to merge all (n) stone piles into one when the initial chosen pile is the ((l+i-1))-th pile.

sample

3 2
1 2 3
1 3
2 2

8 9 11
9