#P17954. Exchange Error

Exchange Error

Exchange Error

题目描述

给定长度为 nn 的整数数组 aa。对于一个整数 xx,把数组的每个元素都加上 xx,并定义

$$S(x)=\max_{1\le l\le r\le n}\sum_{i=l}^{r}(a_i+x).$$

给定 qq 个 xx,分别求出 S(x)S(x)。每个询问都使用原数组 aa,平移量不会在询问之间累积。

所选子数组必须非空,因此答案可能为负数。

输入格式

第一行一个整数 tt,表示测试用例数,1≤t≤2⋅1041\le t\le2\cdot10^4。

每组测试用例包含三行:

  • 第一行两个整数 n,qn,q,1≤n,q≤2⋅1051\le n,q\le2\cdot10^5。
  • 第二行 nn 个整数 a1,…,ana_1,\ldots,a_n,−108≤ai≤108-10^8\le a_i\le10^8。
  • 第三行 qq 个整数,依次为各询问的平移量 xx,−108≤x≤108-10^8\le x\le10^8。

所有测试用例的 nn 之和不超过 2⋅1052\cdot10^5,qq 之和也不超过 2⋅1052\cdot10^5。

输出格式

每组测试用例输出一行 qq 个整数,按询问的输入顺序给出答案。

样例 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

输出

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