有一天,“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)$$$ 是多少。
输入
每个测试包含多个测试用例。第一行包含一个整数 $$$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$$$ 都包含一个整数 $$$k_i$$$ ($$$1 \le k_i \le 10^9$$$) - 学生可以吃多少个披萨的下一个限制。
保证所有输入数据集的 $$$n$$$ 值的总和不超过 $$$5 \cdot 10^4$$$。
保证所有输入数据集的 $$$q$$$ 值的总和不超过 $$$5 \cdot 10^4$$$。
输出
对于每个测试用例,对于学生可以吃多少个披萨的每个限制,输出在确保线路舒适的情况下可以达到的最大值 $$$\max(a_1, a_2, \ldots, a_n)$$$。
示例
输入 #1
3 2 1 10 20 10 6 7 3 1 2 4 5 6 1 2 4 8 16 32 64 10 4 1 2 4 8 16 32 64 128 256 512 10 100 1000 10000
输出 #1
26 7 8 10 12 19 35 67 513 560 1011 10001
注意
在第一组输入数据的第一个查询中,可以先给第一个学生$$$3$$$披萨,然后给第二个学生$$$6$$$披萨,得到最终的数组$$$[13, 26]$$$(这条线很舒服,因为$$$13 \cdot 2 \ge 26$$$),其中最大元素为$$$26$$$。