Mr. Nežmah has started his new gig as a quantitative researcher. He is working with historical data of an unnamed stock on an interval of $$$n$$$ consecutive days. This data is represented as an array $$$a_i$$$, which indicates that the price of the stock moved by $$$a_i$$$ on the $$$i$$$-th day. Just as he was going to start training his model, he noticed there was an error in the data!
The whole array $$$a_i$$$ was shifted by an unknown constant. One of the key features in his model is the largest price change which happened in those $$$n$$$ days. More formally, for an array $$$b$$$ of length $$$n$$$, he is interested in
$$$$$$ \max_{1 \leq l \leq r \leq n}\; b_l + \ldots + b_r $$$$$$
Now, because the data is erroneous, Nežmah wants to calculate this value for different shifts of the array $$$a$$$, or formally
$$$$$$ S(x) := \max_{1 \leq l \leq r \leq n}\; (a_l + x) + \ldots + (a_r + x) $$$$$$
Help Nežmah calculate $$$S(x)$$$ for $$$q$$$ different values of $$$x$$$!
The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 2 \cdot 10^4$$$), the number of test cases.
The first line of each test case contains two integers $$$n$$$ and $$$q$$$($$$1 \leq n,q \leq 2 \cdot 10^5$$$).
The second line of each test case contains the array $$$a$$$($$$-10^8 \leq a_i \leq 10^8$$$).
The third line of each test case contains the $$$q$$$ queries($$$-10^8 \leq x \leq 10^8$$$).
It's guaranteed that the sum of $$$n$$$ and the sum of $$$q$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.
For each test case, output $$$q$$$ numbers: the answers to the queries.
25 71 2 6 9 -40 -1 -20 -2 5 -4 -87 86 -14 1 5 -14 3 -8-5 -3 0 4 5 6 8 9
18 14 -11 11 39 7 1 1 3 6 14 18 23 35 42
