题目描述

光头强有一个有 $n$ 级台阶的楼梯。地面从 $0$ 米开始，第一步高出地面 $a_1$ 米，第 $i$ 步比前一步高出 $a_i$ 米。

光头强有 $q$ 次询问，每次询问用整数 $k_1,…,k_q$ 表示。对于每次询问 $k_i$，你必须输出光头强的腿长为 $k_i$ 时，通过爬台阶可以达到的最大可能高度。光头强只能在腿长至少为 $a_j$ 时爬第 $j$ 级台阶。换言之，如果要爬第 $j$ 级，必须有 $k_i≥a_j$。

注意，每个问题视为独立的。

输入格式

第一行包含单个整数 $t(1≤t≤100)$ 代表测试用例数。

每个测试用例的第一行包含两个整数 $n,q(1≤n,q≤2⋅10^5)$，分别是阶梯数和询问数。

每个测试用例的第二行包含 $n$ 个整数 $(1≤a_i≤10^9)$ 代表台阶高度。

每个测试用例的第三行包含 $q$ 个整数 $(0≤k_i≤10^9)$ 代表每次询问的数字。

保证 $n$ 的和不超过 $2⋅10^5$，$q$ 的和不超过 $2⋅10^5$。

输出格式

对于每个测试用例，输出一行包含 $q$ 个整数，即每次询问的答案。

请注意，答案可能不适合 $32$ 位整数类型，因此您应该在编程语言中至少使用 $64$ 位整数类型。

测试样例

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

样例说明

考虑第一个测试用例，如题目描述中所示。

• 如果光头强的腿长 $1$ 米，那么他只能爬 $1$ 号楼梯，所以他能达到的最高高度是 $1$ 米。
• 如果光头强的腿长 $2$ 或 $4$，那么他只能爬 $1、2$ 和 $3$ 级楼梯，所以他能达到的最高高度是 $1+2+1=4$ 米。
• 如果光头强的腿长 $9$ 或 $10$ 米，那么他可以爬上整个楼梯，所以他能达到的最高点是 $1+2+1+5=9$ 米。

在第二个测试案例的第一个问题中，光头强腿长为 0，所以他甚至连一步都走不上去 :(