Problem Description

You are given a sequence of positive integers $a_i$ of length $n$, indexed starting from $1$. We view this sequence as a ring where the first and last elements are adjacent. More specifically, for two numbers $a_i$ and $a_j$ with indices $i$, $j$ ($i \leqslant j$), their distance is defined as $\min(j-i, i+n-j)$.

Now you are also given $m$ integers $k_1, k_2, \ldots, k_m$. For each $k_i$ ($i=1, 2, \ldots, m$), you need to rearrange the sequence $a_i$ so that the sum of products of every pair of numbers on the ring whose distance is $k_i$ is maximized.

Input Format

The first line contains two positive integers $n$ and $m$, representing the sequence length and the number of queries.

The next line contains $n$ positive integers, representing $a_i$.

The next $m$ lines each contain one non-negative integer, representing $k_i$.

Output Format

Output $m$ lines. Each line contains one integer, representing the answer.

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

91
82
85
88

Hint

Explanation for Sample Input/Output 1

• When $k=0$: the answer is the sum of squares of all numbers.
• When $k=1$: one optimal arrangement is $\{3,1,2,4,6,5\}$. The answer is $3 \times 1 + 1 \times 2 + 2 \times 4 + 4 \times 6 + 6 \times 5 + 5 \times 3 = 82$.
• When $k=2$: one optimal arrangement is $\{3,6,1,4,2,5\}$. The answer is $3 \times 1 + 1 \times 2 + 2 \times 3 + 6 \times 4 + 4 \times 5 + 5 \times 6 = 85$.
• When $k=3$: one valid arrangement is $1,5,3,2,6,4$, and the answer is $88$. Note that the answer here is not $44$.

Constraints and Hints

For all testdata: $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$.

Translated by ChatGPT 5