Ученые планеты Олимпия каждый год исследуют различные мутации геномов примитивных организмов. Геном таких организмов может быть представлен как последовательность 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 ≤ 10^5
, 1 ≤ k ≤ 10^9
), задающих начальный размер генома и количество мутаций, которые геном переживает. Вторая строка содержит n неотрицательных целых чисел, не превосходящих n, - начальный вид генома.
Вывести геном после k мутаций в том же формате, как и на входе: n чисел, разделенных пробелом.