Maximizing Circular Pair Product Sum

You are given a circular sequence of n positive integers \(a_1, a_2, \ldots, a_n\) (indexed from 1). The sequence is considered as a ring so that the element following \(a_n\) is \(a_1\). For any two numbers \(a_i\) and \(a_j\) with \(i \le j\), their circular distance is defined as

[ d(i,j)=\min\bigl(j-i,, i+n-j\bigr). ]

You are then given m queries. In the i-th query a positive integer \(k_i\) is given. For each query you are allowed to arbitrarily rearrange the sequence. Your task is to choose a permutation which maximizes the sum of products of every unordered pair of numbers \((a_i, a_j)\) whose circular distance is exactly \(k_i\); that is, you wish to maximize

[ S=\sum_{1\le i<j\le n,; d(i,j)=k_i} a_i\cdot a_j. ]

Output the maximum possible sum for each query.

Note: When \(n\) is even and \(k_i=n/2\), each pair is counted only once. For other cases every unordered pair with \(d(i,j)=k_i\) is included.

inputFormat

The first line contains two integers \(n\) and \(m\) -- the length of the sequence and the number of queries, respectively.

The second line contains \(n\) positive integers \(a_1, a_2, \ldots, a_n\).

The third line contains \(m\) positive integers \(k_1, k_2, \ldots, k_m\), one for each query.

outputFormat

For each query, output a single line with one integer -- the maximum sum obtainable by rearranging the sequence such that the sum of products \(a_i \cdot a_j\) over all unordered pairs with circular distance exactly \(k_i\) is maximized.

sample

4 2
1 2 3 4
1 2

25
14