Nežmah 先生开始了他作为量化研究员的新工作。他正在研究某只未命名股票在连续 $n$ 天内的历史数据。这些数据用数组 $a_i$ 表示，表示该股票的价格在第 $i$ 天波动了 $a_i$。就在他准备开始训练模型时，他发现数据中存在一个错误！

整个数组 $a_i$ 都被偏移了一个未知的常数。他的模型中的一个关键特征是这 $n$ 天内发生的最大价格变化。更正式地，对于一个长度为 $n$ 的数组 $b$，他感兴趣的是：

$$\max_{1 \le l \le r \le n} b_l + \dots + b_r$$

现在，由于数据有误，Nežmah 想要计算数组 $a$ 在不同偏移量下的该值，即：

$$S(x) := \max_{1 \le l \le r \le n} (a_l + x) + \dots + (a_r + x)$$

请帮助 Nežmah 计算 $q$ 个不同的 $x$ 值对应的 $S(x)$！

输入格式

第一行包含一个整数 $t$ ($1 \le t \le 2 \cdot 10^4$)，表示测试用例的数量。

每个测试用例的第一行包含两个整数 $n$ 和 $q$ ($1 \le n, q \le 2 \cdot 10^5$)。

每个测试用例的第二行包含数组 $a$ ($-10^8 \le a_i \le 10^8$)。

每个测试用例的第三行包含 $q$ 个查询 ($-10^8 \le x \le 10^8$)。

保证所有测试用例中 $n$ 的总和以及 $q$ 的总和均不超过 $2 \cdot 10^5$。

输出格式

对于每个测试用例，输出 $q$ 个数：对应查询的答案。

样例

输入样例 1

2
5 7
1 2 6 9 -4
0 -1 -20 -2 5 -4 -8
7 8
6 -14 1 5 -14 3 -8
-5 -3 0 4 5 6 8 9

输出样例 1

18 14 -11 11 39 7 1
1 3 6 14 18 23 35 42