CF2057F.Formation

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.

有一天，“T世代”的老师们决定对学生们进行纪律教育，于是将他们排成一列，并让他们依次进行计算。总共有 $n$ 名学生，队列中第 $i$ 个学生的身高为 $a_i$。

若对每个从 $1$ 到 $n - 1$ 的 $i$，均满足条件 $a_i \cdot 2 \ge a_{i + 1}$，则称该队列为舒适的。初始时，该队列是舒适的。

老师们不喜欢队列中的最大身高过小，因此打算给学生们披萨吃。已知每名学生每吃一个披萨，其身高就增加 $1$。每个披萨只能由一名学生食用，但每名学生可以吃任意多个披萨。重要的是：所有学生吃完披萨后，队列仍必须保持舒适。

老师们共有 $q$ 种备选方案，表示他们将订购的披萨总数。对每种方案 $k_i$，请回答如下问题：若学生们总共最多吃掉 $k_i$ 个披萨，那么所能达到的最大身高 $\max(a_1, a_2, \ldots, a_n)$ 是多少？

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

每个测试包含多个测试用例。第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。随后是各测试用例的描述。

每个测试用例的第一行包含两个整数 $n$ 和 $q$（$1 \le n, q \le 5 \cdot 10^4$），分别表示学生人数以及教师可能订购的披萨数量的选项个数。

每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le 10^9$），表示各位学生的身高。题目保证初始队列是“舒适的”。

接下来的 $q$ 行（每个测试用例对应 $q$ 行）每行包含一个整数 $k_i$（$1 \le k_i \le 10^9$），表示学生可食用的披萨数量的新上限。

保证所有测试用例中 $n$ 的总和不超过 $5 \cdot 10^4$。

保证所有测试用例中 $q$ 的总和不超过 $5 \cdot 10^4$。

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.

对于每个测试用例，针对学生可食用披萨数量的每个限制，输出在保证队列舒适的前提下所能达到的最大值 $\max(a_1, a_2, \ldots, a_n)$。

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

在第一组输入数据的第一个查询中，你可以先给第一位学生分发 $3$ 个披萨，再给第二位学生分发 $6$ 个披萨，使得最终数组为 $[13, 26]$（该数组是舒适的，因为 $13 \cdot 2 \ge 26$），其最大元素为 $26$。