Cracking the Code

A group of cp enthusiastic students from University of Dhaka were on a fun journey. They brought along a special array passport called $A$ from their university. This passport was a list of $n$ distinct numbers from $1$ to $n$.

As they explored, they discovered a bunch of mysterious boxes. Each box had a number written on it. There were $q$ of these boxes in total. The students knew that these numbers held the key to unlocking the secrets inside the boxes.

To open the boxes and reveal the treasures hidden inside, they had to follow a set of rules. First, they sorted their array passport carefully in ascending order. Then, they needed to reverse part of the sorted list, starting from index $x$ and going to the end of the list.

After each time they followed these rules, they discovered a special code or password that unlocked each of the $q$ mystery boxes. They calculated this password by adding up the numbers in their list, but each number had to be multiplied by its position in the list.

Formally, the password of the box written the number $x$ on top of it is calculated as follows:

• Sort the array $A$

• Reverse $A[x\dots n]$

• Calculate $\sum\limits_{\substack{\text{i=1}}}^nA[i]\cdot i$

Feeling very tired from their long journey, they came to you for help in figuring out how to open the boxes. They showed you their special array passport and the numbers on each of the mystery boxes. Can you give them a hand?

Input

The problem contains multiple test cases.

The first line contains the number of test cases $t$ $(1 \le t\le 10^4)$. The description of the test cases follows-

The first line of each test case contains a single integer $n$ $(1 \le n \le 2\cdot10^5 )$

The second line of each test case contains $n$ space-separated distinct integer from $1$ to $n$ denoting the array passport $A$.

The next line contains an integer $q$ $(1 \le q \le 2\cdot10^5)$ denoting the number of boxes.

Each of the next $q$ lines contain an integer $x$ $(1\le x\le n)$

It is guaranteed that the sum of $n$ over all test cases does not exceed $2\cdot10^5$. It is also guaranteed that the sum of $q$ over all test cases does not exceed $2\cdot10^5$.

Output

For each of the boxes, output the password in a new line.

Sample

Input	Output
1 7 5 4 7 3 6 1 2 5 4 3 6 7 5	130 120 139 140 136
In the sample input, the first box contains the number $4$. After sorting the array: it becomes $[1, 2, 3, 4, 5, 6, 7]$ Reversing the segment $[4\dots 7]$ it becomes $[1, 2, 3, 7, 6, 5, 4]$ So, the password is $1\cdot 1 + 2\cdot 2 + 3\cdot 3 + 7\cdot 4 + 6\cdot 5 + 5\cdot 6 + 4\cdot 7 = 130$