F. Temporary Array
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Da7doo7 is facing this problem in a job interview and needs your help.

You are given an array $$$a$$$ of $$$n$$$ positive integers.

Every second, each of its border elements$$$^\dagger$$$ will decrease exactly by $$$1$$$. If at any moment some elements become zero, they will disappear from the array. For example:

$$$[\underline{1}, 3, \underline{2}] \;\; \xrightarrow[]{\texttt{one second}} \;\; [\underline{3}, \underline{1}] \;\; \xrightarrow[]{\texttt{one second}} \;\; [\underline{2}] \;\; \xrightarrow[]{\texttt{one second}} \;\; [\underline{1}] \;\; \xrightarrow[]{\texttt{one second}} \;\; []$$$

You have to answer $$$q$$$ independent queries. In each query, you are given a number $$$s$$$ and you have to determine how many elements will remain after $$$s$$$ seconds.

$$$^\dagger$$$ An element of an array is considered a border element if and only if it is either the leftmost or rightmost element of the array.

Note

If there is only one element remaining, then each second it will decrease by $$$1$$$, and not $$$2$$$.

Input

The first line of the input contains one integer $$$T$$$ $$$(1\le T\le 10^3)$$$ representing the number of test cases.

The description of the test cases follows.

The first line of each test case contains two integers $$$n$$$ and $$$q$$$ ($$$1\le n, q \le 2\cdot 10^5$$$) denoting the length of the array $$$a$$$ and the number of queries respectively.

The second line of each test case contains $$$n$$$ integers $$$a_1, \ldots, a_n$$$ ($$$1\le a_i\le 10^6$$$) — the elements of array $$$a$$$.

Each of the next $$$q$$$ lines of each test case contains a single integer $$$s$$$ ($$$0\le s\le 10^{12}$$$) — the query.

It is guaranteed that the sum of $$$n$$$ over all test cases, as well as the sum of $$$q$$$, does not exceed $$$2\cdot 10^5$$$.

Output

For each query, output how many elements will remain after $$$s$$$ seconds.

Example
Input
3
5 3
1 4 2 3 5
1
5
2
5 4
1 2 2 1 5
3
5
6
10
1 3
5
4
5
6
Output
4
2
4

3
1
0
0

1
0
0