eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Мутация

Мутация

Лимит времени 1 секунда
Лимит использования памяти 128 MiB

Ученые планеты Олимпия каждый год исследуют различные мутации геномов примитивных организмов. Геном таких организмов может быть представлен как последовательность n неотъемлемых целых чисел, занумерованы слева направо от единицы до n и не превышают число n. Геномы подлежат постоянным мутациям. На каждом этапе мутации геном изменяется следующим образом:

  • на первое место записывается количество единиц во входном геноме;

  • на второе место записывается количество двоек во входном геноме;

  • ...,

  • на место номер n записывается количество чисел, равных n во входном геноме.

Например, геном [1, 2, 3] из трех чисел после мутации преобразуется в [1, 1, 1] - по одной единице, двойке и тройке. Другие примеры:

  • [1, 2, 2, 3, 3, 3] преобразуется в [1, 2, 3, 0, 0, 0]

  • [7, 7, 7, 4, 7, 4, 4] преобразуется в [0, 0, 0, 3, 0, 0, 4]

Далее геном продолжает изменяться по тому же принципу.

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

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

Первая строка содержит два целых числа n и k (1n10^5, 1k10^9), задающих начальный размер генома и количество мутаций, которые геном переживает. Вторая строка содержит n неотрицательных целых чисел, не превосходящих n, - начальный вид генома.

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

Вывести геном после k мутаций в том же формате, как и на входе: n чисел, разделенных пробелом.

Пример

Входные данные #1
4 2
1 3 1 4
Выходные данные #1
2 1 0 0
Источник 2015 XXVIII Всеукраинская олимпиада по информатике