DOS 是一种 Kayzin 发明的单人游戏。游戏开始时，你会得到一排 $n$ 张卡片，每张卡片上都有一个数值 $a_i$。

在每次“匹配”操作中，你可以选择任意两张卡片（假设这两张卡片的下标分别为 $i, j$，且 $i < j$），你将获得 $(a_i + a_j) \times (a_i - a_j)$ 的分数。

Kayzin 会询问你 $m$ 次。在第 $k$ 次询问中，你需要从下标在 $L_k$ 到 $R_k$ 之间的卡片中选择四张卡片，并将这四张卡片组成两对（即进行两次匹配操作，但两次匹配操作所选的卡片下标必须互不相同。也就是说，一张卡片最多只能被匹配一次。例如，如果你选择了下标为 $a, b, c, d$ 的四张卡片，将 $a$ 与 $b$ 匹配，将 $c$ 与 $d$ 匹配，或者将 $a$ 与 $c$ 匹配，将 $b$ 与 $d$ 匹配都是合法的，但将 $a$ 与 $b$ 匹配，同时将 $b$ 与 $c$ 匹配是不合法的）。请计算这两次匹配得分之和的最大值。

注意，各次询问之间是相互独立的。

输入格式

第一行包含一个整数 $T (T \le 100)$，表示测试用例的数量。接下来是 $T$ 个测试用例。

对于每个测试用例： 第一行包含两个整数 $n (4 \le n \le 2 \times 10^5)$ 和 $m (1 \le m \le 10^5)$，$n$ 表示卡片总数，$m$ 表示 Kayzin 询问的次数。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n (1 \le a_i \le 10^8)$，表示每张卡片的数值。 接下来的 $m$ 行包含 Kayzin 的询问。第 $k$ 行包含两个数字 $L_k$ 和 $R_k (1 \le L_k \le R_k \le n)$，输入保证 $R_k - L_k \ge 3$。

保证所有测试用例中 $n$ 的总和不超过 $2 \times 10^5$，且所有测试用例中 $m$ 的总和不超过 $2 \times 10^5$。

输出格式

对于每个测试用例，输出 $m$ 个整数，表示通过选择四张卡片（两对匹配）所能获得的最大分数。

样例

输入 1

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

输出 1

69
-34
53