403045: GYM100981 C Призовой фонд

C. Призовой фондограничение по времени на тест3 секундыограничение по памяти на тест512 мегабайтвводстандартный вводвыводстандартный вывод

Компания ХакерКук провела свой грандиозный чемпионат по спортивному программированию с большим призовым фондом, однако распределение призовых денег до сих пор не объявлено. Единственное, что известно об итоговом распределении, это что участник с более высоким местом получит не меньше призовых денег, чем участник с более низким местом.

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

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

В первой строке входных данных заданы два целых числа n и k (1 ≤ k ≤ n ≤ 1 000 000) — общее количество участников и количество друзей работника ХакерКук.

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

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

Выведите n целых неотрицательных чисел b₁, b₂, ..., b_n (), которые означают, что участник, занявший i-е место, должен получить часть призового фонда.

Если возможных ответов несколько, разрешается вывести любой.

Гарантируется, что существует оптимальный ответ, удовлетворяющий условию, описанному в формате вывода.

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

5 2
1 2

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

2 1 0 0 0

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

2 1
2

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

1 1 

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

3 2
1 3

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

1 0 0 

Примечание

В первом примере весь призовой фонд достанется друзьям хитрого разработчика ХакерКук.

Во втором примере нельзя получить больше, чем половину призового фонда, так как первое место получает приз не меньший, чем второе.