eolymp
bolt
Try our new interface for solving problems
Problems

Mutation

Mutation

Time limit 1 second
Memory limit 128 MiB

The scientists of the planet Olympia each year investigate various mutations of the genomes of primitive organisms. The genome of such organisms can be represented as a sequence of n integers, numbered from left to right from one to n and does not exceed the number n. Genomes are subject to permanent mutations. At each stage of the mutation, the genome changes as follows:

  • the number of ones in the input genome is written to the first place;

  • the number of twos in the input genome is written to the second place;

  • ...,

  • the number of n's in the input genome is written to the n's place;

For example, genome [1, 2, 3] with three integers after mutation transforms to [1, 1, 1] - one one, two and three. Another samples:

  • [1, 2, 2, 3, 3, 3] transforms into [1, 2, 3, 0, 0, 0]

  • [7, 7, 7, 4, 7, 4, 4] transforms into [0, 0, 0, 3, 0, 0, 4]

Further, the genome changes according to the same principle.

Write a program that, given the initial state of genome, determines its state after k mutations.

Input data

First line contains two integers n and k (1n10^5, 1k10^9) giving the initial size of genome and number of genome mutations. Second line contains n nonnegative integers, not exceeding n, - the initial state of genome.

Output data

Print the genome after k mutations in the input format: n space separated integers.

Examples

Input example #1
4 2
1 3 1 4
Output example #1
2 1 0 0
Source 2015 XXVIII All Ukrainian informatics olympiad