F. Линейка
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В один из дней преподаватели «Т-поколения» решили приучить школьников к дисциплине, поэтому поставили их в ряд. Вам известно, что всего есть $$$n$$$ школьников, у $$$i$$$-го по порядку школьника рост равен $$$a_i$$$.

Школьникам комфортно, если для каждого $$$i$$$ от $$$1$$$ до $$$n - 1$$$ выполняется следующее условие: $$$a_i \cdot 2 \ge a_{i + 1}$$$. Изначально школьникам комфортно.

Преподавателям не нравится то, что максимальный рост в ряду слишком маленький, поэтому они хотят накормить школьников пиццей. Если школьник съест одну пиццу, то его рост увеличится на $$$1$$$. Одну пиццу может съесть только один школьник, но каждый школьник может съесть неограниченное количество пицц. Важно, чтобы после того как все школьники съели свои пиццы, школьникам было комфортно.

У преподавателей есть $$$q$$$ вариантов того, сколько пицц они закажут. Для каждого варианта $$$k_i$$$ ответьте на вопрос: какой максимальный рост $$$\max(a_1, a_2, \ldots, a_n)$$$ можно получить, если школьники съедят не более $$$k_i$$$ пицц.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$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)$$$, которое можно получить, чтобы школьникам было комфортно.

Пример
Входные данные
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
Выходные данные
26
7 8 10 12 19 35 67
513 560 1011 10001
Примечание

В первом запросе первого набора входных данных можно сначала дать $$$3$$$ пиццы первому школьнику, а потом второму школьнику $$$6$$$ пицц, тогда итоговый массив станет $$$[13, 26]$$$ (школьникам комфортно, так как $$$13 \cdot 2 \ge 26$$$), максимальный элемент в нем равен $$$26$$$.