One day, the teachers of "T-generation" decided to instill discipline in the pupils, so they lined them up and made them calculate in order. There are a total of $$$n$$$ pupils, the height of the $$$i$$$-th pupil in line is $$$a_i$$$.

The line is comfortable, if for each $$$i$$$ from $$$1$$$ to $$$n - 1$$$, the following condition holds: $$$a_i \cdot 2 \ge a_{i + 1}$$$. Initially, the line is comfortable.

The teachers do not like that the maximum height in the line is too small, so they want to feed the pupils pizza. You know that when a pupil eats one pizza, their height increases by $$$1$$$. One pizza can only be eaten by only one pupil, but each pupil can eat an unlimited number of pizzas. It is important that after all the pupils have eaten their pizzas, the line is comfortable.

The teachers have $$$q$$$ options for how many pizzas they will order. For each option $$$k_i$$$, answer the question: what is the maximum height $$$\max(a_1, a_2, \ldots, a_n)$$$ that can be achieved if the pupils eat at most $$$k_i$$$ pizzas.

Input

Each test contains multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases. The description of the test cases follows.

The first line of each set of test case contains two integers $$$n$$$ and $$$q$$$ ($$$1 \le n, q \le 5 \cdot 10^4$$$) — the number of pupils and the number of options for how many pizzas the teachers will order.

The second line of each set of test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — the heights of the pupils.It is guaranteed that initially, the line is comfortable.

Each of the following $$$q$$$ lines of each set of input data contains one integer $$$k_i$$$ ($$$1 \le k_i \le 10^9$$$) — the next limit for how many pizzas the pupils can eat.

It is guaranteed that the sum of the values of $$$n$$$ across all sets of input data does not exceed $$$5 \cdot 10^4$$$.

It is guaranteed that the sum of the values of $$$q$$$ across all sets of input data does not exceed $$$5 \cdot 10^4$$$.

Output

For each test case, for each limit for how many pizzas the pupils can eat, output the maximum value $$$\max(a_1, a_2, \ldots, a_n)$$$ that can be achieved while ensuring that the line is comfortable.

Note

In the first query of the first set of input data, you can first give $$$3$$$ pizzas to the first pupil, and then give $$$6$$$ pizzas to the second pupil, making the final array $$$[13, 26]$$$ (the line is comfortable since $$$13 \cdot 2 \ge 26$$$), and the maximum element in it is $$$26$$$.

Formation

Examples