A long time ago, Little M and his friend Little N prepared a programming contest together. They came up with $n$ problems in total, numbered $1 \sim n$, where the quality of the $i$-th problem ($1 \le i \le n$) is a non-negative integer $a_i$.

Time flies. Today, Little M is no longer a contestant in the Informatics Olympiad, but they once agreed to host a series of contests together. Little M has not forgotten this.

Now, Little M wishes to divide these $n$ problems into several training contests, which means partitioning the $n$ problems into several contiguous intervals. A partition scheme can be represented by a sequence of integers: $0 = r_0 < r_1 < r_2 < \dots < r_k = n$, indicating that there will be $k$ training contests, where the $i$-th training contest contains all problems with indices from $(r_{i-1} + 1)$ to $r_i$ (inclusive).

Furthermore, Little M wants to provide the best possible contests for the participants. Little M observed that the quality of a contest is determined by both its best problem and its last problem. Therefore, he stipulates: the quality of a training contest is the product of the maximum value of $a_i$ among the problems it contains and the value of $a_i$ of the problem with the largest index it contains.

Little M has not yet decided on the number of contests. Currently, there are only $q$ candidate values $k_1, k_2, \dots, k_q$. Little M wants to know, for each $1 \le j \le q$, among all ways to partition the problems into exactly $k_j$ training contests, what is the maximum possible sum of the qualities of all training contests.

Input

The input is read from standard input. The first line contains a positive integer $t$, representing the number of test cases. The following lines contain the test cases. For each test case: The first line contains two positive integers $n, q$. The second line contains $n$ non-negative integers $a_1, a_2, \dots, a_n$. * The third line contains $q$ positive integers $k_1, k_2, \dots, k_q$.

Output

For each test case, output a single line containing $q$ non-negative integers, where the $j$-th ($1 \le j \le q$) integer represents the maximum sum of the qualities of all training contests among all ways to partition the problems into exactly $k_j$ training contests.

Examples

Input 1

2
4 3
3 2 4 1
3 1 4
5 5
5 10 3 16 8 7
1 2 3 4 5

Output 1

26 4 30
112 312 412 469 478

Subtasks

For all test cases, it is guaranteed that: $1 \le n, \sum n \le 5 \times 10^5$, $1 \le q, \sum q \le 10^5$; For all $1 \le i \le n$, $0 \le a_i \le 10^6$; * For all $1 \le j \le q$, $1 \le k_j \le n$.