Метро — интересное место, в особенности, зимой.

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

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

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

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

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

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

Формат входных данных

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

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

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

Формат выходных данных

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

Пример