8496: DOS Card

DOS is a new single-player game that Kayzin came up with. At the beginning of the game you will be given n cards in a row, each with the number of value ai.

In each "matching" operation you can choose any two cards (we assume that the subscripts of these two cards are i,j (i < j). Notice that i is less than j), and you will get a score of (ai+aj)×(ai−aj).

Kayzin will ask you $m$ times. In the k-th query, you need to select four cards from the cards with subscripts Lk to Rk, and "match" these four cards into two pairs (i.e., two matching operations, but the subscripts of the cards selected in the two matching operations must be different from each other. That is, a card can only be matched at most once. e.g., if you select four tickets with subscripts a  b, c , and d , matching a with b and c with d, or matching a with c and b with d are legal, but matching a with b and b with c is not legal), please calculate the maximum value of the sum of the two matching scores.

Note that the queries are independent of each other.

The first line contains an integer T(T≤100). Then T test cases follow. For one case,

The first line contains two integer (4≤n≤2×105) and m (1≤m≤10^5) , $n$ denotes the total number of cards , $m$ denotes the number of times Kayzin queries.

The second line contains n integers a1,a2,…,an (1≤ai≤10^8), denotes the value of each card.

The next $m$ lines contain Kayzin's queries. The kth line has two numbers, Lk and Rk (1≤Lk≤Rk≤n), the input guarantees that Rk−Lk≥3.

It is guaranteed that the sum of n over all test cases doesn't exceed 2×10^5 and the sum of m over all test cases doesn't exceed 2×10^5.