Ліфт#3008

Ліфт

2 секунди

64 мегабайти

Складна

У центрі Нью-Донецька збудовано хмарочос з надзвичайно великою кількістю поверхів, включаючи велику підземну частину. Зайшовши з вулиці, людина потрапляє на поверх $0$ . Поверхи вище нього пронумеровані додатними цілими числами, а нижче — від’ємними цілими числами. У хмарочосі встановлений ліфт, але з певних причин він не може зупинятися на деяких поверхах. У ліфта є дві кнопки: «вгору» та «вниз». Натискання кнопки «вгору» піднімає ліфт на найближчий поверх, де він може зупинитися, а натискання «вниз» — опускає ліфт на найближчий такий поверх униз. Кількаразове натискання кнопки призводить до виконання дії відповідну кількість разів поспіль без зупинок на проміжних поверхах. Хлопчик на ім’я Вася вирішив покататися на ліфті. Він увійшов на нульовому поверсі і почав натискати на кнопки.

Ваше завдання — знайти послідовність поверхів, на яких зупиниться ліфт після кожної з Васиних команд.

Вхідні дані

У першому рядку дано два цілі числа $K$ і $N$ ( $0 \leq K, N \leq 1 0^{5}$ 0 \leq K, N \leq 10^5): кількість поверхів, на яких ліфт не зупиняється, і кількість рухів ліфта відповідно. У другому рядку міститься $K$ цілих чисел $l_{1}, l_{2}, \dots, l_{K}$ l_1, l_2, \dots, l_K ( $- 1 0^{9} \leq l_{1} < \dots < l_{K} \leq 1 0^{9}$ -10^9 \leq l_1 < \dots < l_K \leq 10^9) — номери цих поверхів. Гарантується, що серед них немає $0$ . У третьому рядку дано $N$ цілих чисел, кожне з яких означає команду, яку Вася подав у ліфті. Знак числа визначає кнопку (додатне — «вгору», від’ємне — «вниз»), а модуль — кількість натискань. Усі числа не перевищують за модулем $1 0^{6}$ 10^6.

Вихідні дані

Виведіть $N$ чисел — номери поверхів, на яких ліфт зупиниться після кожної з Васиних команд.

Приклади

Приклад 1