Codeforces Round 827 (Div. 4) |
---|
Finished |
Timur has a stairway with $$$n$$$ steps. The $$$i$$$-th step is $$$a_i$$$ meters higher than its predecessor. The first step is $$$a_1$$$ meters higher than the ground, and the ground starts at $$$0$$$ meters.
Timur has $$$q$$$ questions, each denoted by an integer $$$k_1, \dots, k_q$$$. For each question $$$k_i$$$, you have to print the maximum possible height Timur can achieve by climbing the steps if his legs are of length $$$k_i$$$. Timur can only climb the $$$j$$$-th step if his legs are of length at least $$$a_j$$$. In other words, $$$k_i \geq a_j$$$ for each step $$$j$$$ climbed.
Note that you should answer each question independently.
The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 100$$$) — the number of test cases.
The first line of each test case contains two integers $$$n, q$$$ ($$$1 \leq n, q \leq 2\cdot10^5$$$) — the number of steps and the number of questions, respectively.
The second line of each test case contains $$$n$$$ integers ($$$1 \leq a_i \leq 10^9$$$) — the height of the steps.
The third line of each test case contains $$$q$$$ integers ($$$0 \leq k_i \leq 10^9$$$) — the numbers for each question.
It is guaranteed that the sum of $$$n$$$ does not exceed $$$2\cdot10^5$$$, and the sum of $$$q$$$ does not exceed $$$2\cdot10^5$$$.
For each test case, output a single line containing $$$q$$$ 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++).
34 51 2 1 51 2 4 9 102 21 10 13 11000000000 1000000000 10000000001000000000
1 4 4 9 9 0 2 3000000000
Consider the first test case, pictured in the statement.
Name |
---|