eolymp
Задачі

Мутація

Мутація

Вчені планети Олімпія кожен рік досліджують різноманітні мутації геномів примітивних організмів. Геном таких організмів може бути представлений як послідовність 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 (1n105, 1k109), що задають початковий розмір геному та кількість мутацій, які геном переживе. Другий рядок містить n невід’ємних цілих чисел, що не перевищують n, - початковий вигляд геному.

Вихідні дані

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

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB
Вхідні дані #1
4 2
1 3 1 4
Вихідні дані #1
2 1 0 0

Пояснення: Спочатку [1, 3, 1, 4] мутує в геном [2, 0, 1, 1], який у свою чергу мутує в [2, 1, 0, 0].

Джерело 2015 XXVIII Всеукраїнська олімпіада з інформатики