2448: cf1742e - Scuza
Description
Timur has a stairway with nn steps. The ii-th step is aiai meters higher than its predecessor. The first step is a1a1 meters higher than the ground, and the ground starts at 00 meters.
The stairs for the first test case.
Timur has qq questions, each denoted by an integer k1,…,kqk1,…,kq. For each question kiki, you have to print the maximum possible height Timur can achieve by climbing the steps if his legs are of length kiki. Timur can only climb the jj-th step if his legs are of length at least ajaj. In other words, ki≥ajki≥aj for each step jj climbed.
Note that you should answer each question independently.
The first line contains a single integer tt (1≤t≤1001≤t≤100) — the number of test cases.
The first line of each test case contains two integers n,qn,q (1≤n,q≤2⋅1051≤n,q≤2⋅105) — the number of steps and the number of questions, respectively.
The second line of each test case contains nn integers (1≤ai≤1091≤ai≤109) — the height of the steps.
The third line of each test case contains qq integers (0≤ki≤1090≤ki≤109) — the numbers for each question.
It is guaranteed that the sum of nn does not exceed 2⋅1052⋅105, and the sum of qq does not exceed 2⋅1052⋅105.
For each test case, output a single line containing qq integers, the answer for each question.
Please note, that the answer for some questions won't fit into 32-bit integer type, so you should use at least 64-bit integer type in your programming language (like long long for C++).
Sample Input Copy
3
4 5
1 2 1 5
1 2 4 9 10
2 2
1 1
0 1
3 1
1000000000 1000000000 1000000000
1000000000
Sample Output Copy
1 4 4 9 9
0 2
3000000000
HINT
Consider the first test case, pictured in the statement.
- If Timur's legs have length 11, then he can only climb stair 11, so the highest he can reach is 11 meter.
- If Timur's legs have length 22 or 44, then he can only climb stairs 11, 22, and 33, so the highest he can reach is 1+2+1=41+2+1=4 meters.
- If Timur's legs have length 99 or 1010, then he can climb the whole staircase, so the highest he can reach is 1+2+1+5=91+2+1+5=9 meters.