[Solution] Scuza Codeforces Solution | Solution Codeforces

E. Scuza

time limit per test

3 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

Timur has a stairway with 𝑛$n$ steps. The 𝑖$i$-th step is 𝑎𝑖$a_i$ meters higher than its predecessor. The first step is 𝑎1$a_1$ meters higher than the ground, and the ground starts at 0$0$ meters.

The stairs for the first testcase.

Timur has 𝑞$q$ questions, each denoted by an integer 𝑘1,…,𝑘𝑞$k_1,\dots ,k_q$. For each question 𝑘𝑖$k_i$, you have to print the maxmimum 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\ge a_j$ for each step 𝑗$j$ climbed.

Note that you should answer each question independently.

Input

The first line contains a single integer 𝑡$t$ (1≤𝑡≤100$1\le t\le 100$) — the number of test cases.

The first line of each test case contains two integers 𝑛,𝑞$n,q$ (1≤𝑛,𝑞≤2⋅105$1\le n,q\le 2\cdot {10}^5$) — the number of steps and the number of questions, respectively.

The second line of each test case contains 𝑛$n$ integers (1≤𝑎𝑖≤109$1\le a_i\le {10}^9$) — the height of the steps.

The third line of each test case contains 𝑞$q$ integers (0≤𝑘𝑖≤109$0\le k_i\le {10}^9$) — the numbers for each question.

It is guaranteed that the sum of 𝑛$n$ does not exceed 2⋅105$2\cdot {10}^5$, and the sum of 𝑞$q$ does not exceed 2⋅105$2\cdot {10}^5$.

Output

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++).

Note

Consider the first test case, pictured in the statement.

• If Timur's legs have length 1$1$, then he can only climb stair 1$1$, so the highest he can reach is 1$1$ meter.
• If Timur's legs have length 2$2$ or 4$4$, then he can only climb stairs 1$1$, 2$2$, and 3$3$, so the highest he can reach is 1+2+1=4$1+2+1=4$ meters.
• If Timur's legs have length 9$9$ or 10$10$, then he can climb the whole staircase, so the highest he can reach is 1+2+1+5=9$1+2+1+5=9$ meters.

In the first question of the second test case, Timur has no legs, so he cannot go up even a single step. :(