Source: Super League of Chinese College Students Algorithm Design 2022, Contest 2 by HDU.

Problem Description

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 $a_i$.

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 $(a_i+a_j)\times (a_i-a_j)$.

Kayzin will ask you $m$ times. In the k-th query, you need to select four cards from the cards with subscripts $L_k$ to $R_k$, 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.

Input

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

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

The second line contains $n$ integers $a_1,a_2,…,a_n$ $(1\le a_i\le 10^8)$, denotes the value of each card.

The next $m$ lines contain Kayzin's queries. The $k$th line has two numbers, $L_k$ and $R_k$ $(1\le L_k\le R_k\le n)$, the input guarantees that $R_k-L_k\ge 3$.

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

Output

Print $m$ integer for each case, indicating the maximum scores that can be obtained by selecting four cards (two matching pairs).

Sample

1
5 3
5 3 2 8 4
1 5
1 4
2 5

69
-34
53