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