Коровы Фермера Джона любят конфетные трости. У ФД \(N\) коров с определённой
начальной высотой. Он хочет скормить им \(M\) конфетных тростей, различной высоты
(\(1\le N,M\le 2\cdot 10^5\)).
ФД планирует кормить коров конфетными тростями одну за одной в порядке, в котором
они заданы на вводе. Чтобы кормить коров ФД вывешивает конфетные трости так, чтобы
изначально они касались земли. Коровы выстраиваются одна за одной в порядке, как они
заданы на входе. Каждая ест до своей высоты (потому что выше не достаёт).
Трость остаётся на месте где она изначально была подвешена и не опускается к земле,
даже после того как её нижняя часть съедена. Возможно, что когда подойдёт очередь
некоторой коровы она ничего не сможет съест, если нижняя часть трости уже выше высоты
этой коровы. После того как пройдёт очередь всех коров, они подрастают на высоту
равную количеству единиц трости, которую съела корова, а ФД вывешивает новую конфетную
трость и коровы повторяют процесс опять (корова 1 всегда начинает есть первой).
ФОРМАТ ВВОДА (с клавиатуры):
Первая строка содержит
\(N\) и
\(M\).
Следующая строка содержит начальные высоты \(N\) коров, каждая в интервале
\([1,10^9]\).
Следующая строка содержит высоты \(M\) конфетных тростей, каждая в интервале
\([1,10^9]\).
ФОРМАТ ВЫВОДА (на экран):
Финальные высоты каждой из
\(N\) коров на отдельной строке.
Заметим, что значения, заданные в тестах могут потребовать использования
64-битного целого типа (например, "long long" в C/C++).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 2
3 2 5
6 1
|
7
2
7
|