410152: GYM103965 F Вежливость в метро

F. Вежливость в метроограничение по времени на тест1 секундаограничение по памяти на тест256 мегабайтвводстандартный вводвыводстандартный вывод

Метро — интересное место, в особенности, осенью.

Изначально все сидячие места в метро были заняты $$$n$$$ обычными пассажирами. Начиная с момента времени $$$0$$$, в вагоне перестают появляться новые обычные пассажиры, но иногда заходят беременные женщины, пожилые люди и пассажиры с детьми, которым следует уступать места.

Пассажир с номером $$$i$$$ раз в $$$a_i$$$ минут отрывается от телефона. Если в это время он видит стоящего человека, которому следует уступить место, то немедленно встает, освобождает место и больше никогда не садится. Если при этом несколько пассажиров встают в один и тот же момент ради меньшего числа привилегированных пассажиров, то всё равно все уступают места и больше не садятся (из чувства солидарности).

За все время в поезд садится $$$m$$$ привилегированных пассажиров, причем $$$i$$$-й из них заходит в момент времени $$$b_i$$$. Поскольку сидячие места для них могут освобождаться не сразу, то они соблюдают очередность, и ранее вошедший привилегированный пассажир (при равенстве времен входа — с меньшим номером) садится раньше. При этом если для вошедшего пассажира находится уже освобожденное ранее место сразу, как он входит, он успевает занять это место до того, как обычные пассажиры отвлекутся от телефонов.

Формально, порядок действий в каждую минуту следующий:

1. привилегированные пассажиры входят в вагон;
2. те из них (с меньшими номерами), для кого хватает уже свободных мест, садятся;
3. если еще остались стоящие привилегированные пассажиры, обычные пассажиры, которые отвлекутся от телефонов в эту минуту, встанут и освободят свои места.

Для каждого из зашедших привилегированных пассажиров найдите время, в которое он сможет занять сидячее место.

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

В первой строке ввода через пробел даны два целых числа $$$n$$$ и $$$m$$$ — количество обычных и привилегированных пассажиров, соответственно ($$$1 \leqslant m \leqslant n \leqslant 10^5$$$).

В следующей строке через пробел перечислены $$$n$$$ целых чисел $$$a_i$$$ — длины периодов, с которыми обычные пассажиры отрываются от телефонов ($$$1 \leqslant a_i\leqslant 10^5$$$).

В последней строке через пробел перечислены $$$m$$$ целых чисел $$$b_i$$$ — времена входа беременных женщин, пожилых людей и пассажиров с детьми ($$$1 \leqslant b_i \leqslant 10^5$$$). Гарантируется, что последовательность $$$b_i$$$ неубывающая, то есть для любых $$$i < j$$$ верно $$$b_i \leqslant b_j$$$.

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

В единственной строке через пробел выведите $$$m$$$ чисел — времена, в которые каждый новый пассажир займет сидячее место.

ПримерыВходные данные

3 2
3 1 2
2 4

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

2 4 

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

5 3
1 2 3 6 7
10 15 20

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

10 15 21