Западная и Восточная Кукуляндия близки к началу войны. Сверхдержавы борются за превосходство в области ядерного оружия, чтобы добиться доминирования в военной сфере. К сожалению, производство и хранение ядерных боеголовок стоит огромных денег и может легко подорвать бюджеты обеих стран.

Военные аналитики и экономисты Западной Кукуляндии предоставили отчёт, согласно которому страна будет в безопасности, а бюджет — в норме, если к концу i-го месяца на складах будет храниться ровно a_i боеголовок. Президент приказал придерживаться этих цифр, и заводы Западной Кукуляндии каждый месяц производят или утилизируют нужное количество боеголовок.

Но разведка Восточной Кукуляндии не дремлет! В начале i-го месяца агенты Восточной Кукуляндии узнают и передают на родину планы Западной Кукуляндии на ближайшие m месяцев, то есть, числа a_i, a_i + 1, …, a_{i + m − 1}. Получив эту информацию, диктатор Восточной Кукуляндии сразу же отдаёт приказ изменить текущее количество боеголовок на складах Восточной Кукуляндии на число x_i. Он выбирает x_i таким образом, что если Восточная Кукуляндия будет m месяцев подряд изменять количество боеголовок на x_i, то в конце каждого месяца у неё будет не меньше боеголовок, чем у Западной Кукуляндии. При этом диктатор тоже заботится о бюджете страны, поэтому выбирает x_i минимально возможным.

Определите, какие приказы будет отдавать диктатор Восточной Кукуляндии в течение первых n месяцев. Можете считать, что к началу первого месяца ни Западная, ни Восточная Кукуляндия не располагают ядерным арсеналом.

В первой строке через пробел записаны целые числа n и m (1 ≤ n ≤ 10000; 1 ≤ m ≤ 50). Во второй строке через пробел записаны целые числа a₁, …, a_{n + m − 1} (0 ≤ a_i ≤ 10⁵) — планы Западной Кукуляндии.

Выведите через пробел целые числа x₁, …, x_n. Число x_i соответствует приказу, который должен отдать диктатор Восточной Кукуляндии в начале i-го месяца.