K. Stock Trading
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Alice is a quantitative trader. She is backtesting a high-frequency trading strategy now. Given a stock's price sequence at $$$n$$$ time points, denoted as $$$v_1, v_2, \ldots, v_n$$$.

The trading bot Alice has set up is controlled by two parameters: a buy threshold $$$a$$$ and a sell threshold $$$b$$$ ($$$a \lt b$$$), and strictly follows the following rules:

  • If the price of the stock at a given time $$$v_i \le a$$$, the bot will buy exactly $$$1$$$ share;
  • If the price of the stock at a given time $$$v_i \ge b$$$, and the bot currently holds at least $$$1$$$ share, the bot will immediately sell $$$1$$$ share;
  • At each time point, the bot can buy or sell at most $$$1$$$ share;
  • After the transaction at the $$$n$$$-th time point is completed, if the robot still holds unsold shares, a forced liquidation mechanism is triggered, selling all remaining shares at the price $$$v_n$$$.

Given a fixed buy threshold $$$a$$$, there are $$$m$$$ independent queries, each specifying a sell threshold $$$b$$$. For each query, please help Alice calculate the total profit under this strategy (total proceeds from sales minus total costs from purchases).

Input

The first line contains a positive integer $$$T$$$ ($$$1 \le T \le 10^4$$$), the number of test cases.

For each test case, the first line contains two positive integers $$$n, a$$$ ($$$1 \le n \le 2 \times 10^5$$$, $$$1 \le a \lt 10^9$$$), representing the number of time points and the buy threshold.

The second line contains $$$n$$$ integers $$$v_1, v_2, \ldots, v_n$$$ ($$$1 \le v_i \le 10^9$$$), giving the historical stock prices at each time point in chronological order.

The third line contains an integer $$$m$$$ ($$$1 \le m \le 2 \times 10^5$$$), representing the number of queries.

The next line contains $$$m$$$ integers $$$b_1, b_2, \ldots, b_m$$$ ($$$a \lt b_i \le 10^9$$$), representing the sell threshold for each query.

It is guaranteed that over all test cases, the sum of $$$n$$$ and the sum of $$$m$$$ do not exceed $$$2 \times 10^5$$$.

Output

For each test case, output one line containing $$$m$$$ integers separated by spaces, representing the final profit of the trading strategy for each query.

Example
Input
2
5 10
5 8 15 12 1
3
11 13 16
6 10
5 5 15 12 20 11
3
11 13 16
Output
14 3 -11
17 25 21
Note

For the first query on the first test case ($$$a=10, b=11$$$), the trading process is as follows:

  1. $$$v_1=5 \lt a$$$: Buy 1 share, cumulative profit $$$-5$$$, holding $$$1$$$ share;
  2. $$$v_2=8 \lt a$$$: Buy 1 share, cumulative profit $$$-13$$$, holding $$$2$$$ shares;
  3. $$$v_3=15 \gt b$$$: Sell 1 share, cumulative profit $$$2$$$, holding $$$1$$$ share;
  4. $$$v_4=12 \gt b$$$: Sell 1 share, cumulative profit $$$14$$$, holding $$$0$$$ shares;
  5. $$$v_5=1 \lt a$$$: Buy 1 share, cumulative profit $$$13$$$, holding $$$1$$$ share;
  6. Liquidation: Sell the remaining $$$1$$$ share at $$$v_5=1$$$, final profit $$$14$$$.