题目描述

给定一个长度为 $n$ 的正整数序列 $a_i$，下标从 $1$ 开始编号。我们将该序列视为一个首尾相邻的环，更具体地，对于下标为 $i$, $j(i \leqslant j)$ 的两个数 $a_i$, $a_j$，它们的距离为 $\min(j-i, i+n-j)$。

现在再给定 $m$ 个整数 $k_1$, $k_2$,..., $k_m$，对每个 $k_i(i=1$, $2$,..., $m)$，你需要将上面的序列 $a_i$ 重新排列，使得环上任意两个距离为 $k_i$ 的数字的乘积之和最大。

输入格式

第一行两个正整数 $n$, $m$，表示序列长度与询问数。

接下来一行 $n$ 个正整数表示 $a_i$。

接下来 $m$ 行每行一个非负整数表示 $k_i$。

输出格式

共 $m$ 行，每行一个整数表示答案。

6 4
1 2 3 4 5 6
0
1
2
3

91
82
85
88

输入输出样例 1 解释

• $k=0$ 时：答案为每个数平方的和。
• $k=1$ 时：一种最优方案：$\{3,1,2,4,6,5\}$。答案为 $3 \times 1 + 1 \times 2 + 2 \times 4 + 4 \times 6 + 6 \times 5 + 5 \times 3 = 82$。
• $k=2$ 时：一种最优方案：$\{3,6,1,4,2,5\}$。答案为 $3 \times 1 + 1 \times 2 + 2 \times 3 + 6 \times 4 + 4 \times 5 + 5 \times 6 = 85$。
• $k=3$ 时，一个合法的排列是 $1,5,3,2,6,4$ ，答案为 $88$。注意这里答案不是 $44$。

数据范围与提示

对于所有测试数据：$1 \leqslant m \leqslant n \leqslant 2 \times 10^5$，$0 \leqslant k \leqslant \lfloor n/2\rfloor$，$1 \leqslant a_i \leqslant 10^5$。