Мутация
Мутация
Ученые планеты Олимпия каждый год исследуют различные мутации геномов примитивных организмов. Геном таких организмов может быть представлен как последовательность 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 (1 ≤ n ≤ 105
, 1 ≤ k ≤ 109
), задающих начальный размер генома и количество мутаций, которые геном переживает. Вторая строка содержит n неотрицательных целых чисел, не превосходящих n, - начальный вид генома.
Выходные данные
Вывести геном после k мутаций в том же формате, как и на входе: n чисел, разделенных пробелом.
4 2 1 3 1 4
2 1 0 0
Şərh: Сначала [1, 3, 1, 4] мутирует в геном [2, 0, 1, 1], который в свою очередь мутирует в [2, 1, 0, 0].