Пожалуйста, прочтите новое правило об ограничении использования AI-инструментов. ×

E. Scuza
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Тимура есть лестница с $$$n$$$ ступеньками. Ступенька $$$i$$$ выше предыдущей на $$$a_i$$$ метров. Первая ступенька на $$$a_1$$$ метр выше земли, а земля находится на высоте $$$0$$$ метров.

Лестница из первого примера.

У Тимура есть $$$q$$$ запросов, каждый из которых обозначается целым числом $$$k_1, \dots, k_q$$$. Для каждого запроса $$$k_i$$$ выведите максимально возможную высоту, на которую Тимур может подняться, поднимаясь по ступенькам, если длина его ног $$$k_i$$$. Тимур может подняться на $$$j$$$-ю ступеньку только в том случае, если длина его ног не меньше $$$a_j$$$. Другими словами, $$$k_i \geq a_j$$$ для каждой ступеньки $$$j$$$.

Обратите внимание, что вы должны ответить на каждый вопрос независимо.

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

Первая строка содержит одно целое число $$$t$$$ ($$$1 \leq t \leq 100$$$) — количество наборов входных данных.

Первая строка каждого набора содержит два целых числа $$$n, q$$$ ($$$1 \leq n, q \leq 2\cdot10^5$$$) — количество ступенек и количество запросов, соответственно.

Вторая строка каждого набора содержит $$$n$$$ целых чисел ($$$1 \leq a_i \leq 10^9$$$) — разницы в высотах ступенек.

Третья строка каждого теста содержит $$$q$$$ целых чисел ($$$0 \leq k_i \leq 10^9$$$) — числа для каждого запроса.

Гарантируется, что сумма $$$n$$$ не превышают $$$2\cdot10^5$$$, сумма $$$q$$$ не превышают $$$2\cdot10^5$$$.

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

Для каждого набора выведите $$$q$$$ целых чисел - ответ на каждый запрос.

Обратите внимание, что ответ на некоторые запросы не помещается в 32-битный целочисленный тип, поэтому вы должны использовать как минимум 64-битный целочисленный тип в вашем языке программирования (например, long long для C++).

Пример
Входные данные
3
4 5
1 2 1 5
1 2 4 9 10
2 2
1 1
0 1
3 1
1000000000 1000000000 1000000000
1000000000
Выходные данные
1 4 4 9 9 
0 2 
3000000000
Примечание

Рассмотрим первый пример, изображенный в условии.

  • Если длина ног Тимура $$$1$$$, то он может подняться только на ступеньку $$$1$$$, поэтому максимальная высота, на которую он может забраться это $$$1$$$ метр.
  • Если длина ног Тимура $$$2$$$ или $$$4$$$, то он может подняться только по ступенькам $$$1$$$, $$$2$$$ и $$$3$$$, поэтому максимальная высота, на которую он может забраться это $$$1+2+1=4$$$ метра.
  • Если длина ног Тимура составляет $$$9$$$ или $$$10$$$, то он может подняться по всей лестнице, так максимальная высота, на которую он может забраться это $$$1+2+1+5=9$$$ метров.
В первом вопросе второго тестового примера у Тимура нет ног, поэтому он не может подняться даже на одну ступеньку. :(