题面翻译

有 $n$ 阶楼梯，当前楼梯与上一阶楼梯的高度差为 $a_i$（$a_1$ 就是第一节阶梯的高度）。

$q$ 次询问，对于每一个 $k_i\ (1\le i \le q)$，若 Timur 一步能提高 $k_i$ 的高度（无法上高度差超过 $k_i$ 的台阶），求出他能到达的最高高度。

输入格式

第一行为一个整数 $t$ ( $1 \leq t \leq 100$ ) 表示数据组数。

对于每组数据：

第一行包括两个整数 $n, q$ ( $1 \leq n, q \leq 2\cdot10^5$ )

第二行包括 $n$ 个整数 $a_1\sim a_n$ ( $1 \leq a_i \leq 10^9$ )

第三行包括 $q$ 个整数 $k_1\sim k_q$( $0 \leq k_i \leq 10^9$ )

保证 $t$ 组数据的 $n$ 之和不超过 $2\cdot10^5$，$q$ 之和也不超过 $2\cdot10^5$。

输出格式

对于每组数据，都输出一行 $q$ 个空格隔开的正整数，即 $q$ 个询问的答案。

3
4 5
1 2 1 5
1 2 4 9 10
2 2
1 1
0 1
3 1
1000000000 1000000000 1000000000
1000000000

1 4 4 9 9 
0 2 
3000000000

提示

第一组数据的情况如前面图片所示

• 若 Timur 一步能提高 $1$ 的高度，他只能爬到第一阶台阶上，所以最大的高度为 $1$
• 若 Timur 一步能提高 $2\sim 4$ 的高度，他只能爬前三阶台阶，所以最大的高度为 $1+2+1=4$
• 若 Timur 一步能提高 $9\sim 10$ 的高度，他能爬所有台阶，所以最大的高度为 $1+2+1+5=9$

来源

• https://www.luogu.com.cn/problem/CF1742E
• https://codeforces.com/problemset/problem/1742/E