Peanut has recently taught his cats how to count from 1 to K. As such, he is very excited and wants to hear them count all at once!
However, cats are inherently very chaotic. Peanut gives his cats a total time period of N seconds to complete counting. Each cat starts counting from a certain integer number of seconds from the beginning of this time period, and shouts one number every second, until it reaches K, after which it stops counting.
As all the cats are shouting at the same time, it is difficult for Peanut to decipher the individual noises. In each second, Peanut can only hear the number that the most number of cats are shouting. If two different numbers are being shouted by the same number of cats, Peanut will only hear the smaller number.
Given a list of N numbers that Peanut can hear for each individual second, Peanut wants to know, for each second, how many cats started counting in that second. If there is more than one solution, output the one that minimises the total number of cats Peanut has, as Peanut is very very sure he doesn't have that many cats. If multiple solutions have the same number of cats, output any of them. It is guaranteed at least one valid solution exists.
The first line of input will contain two integers, N and K.
The second line of input will contain N integers, with the ith integer representing the number Peanut hears in the ith second.
The output should contain N integers, with the ith integer representing how many cats have started shouting at time i.
Any valid solution where the total number of cats does not exceed 1018 will be given 50% for the subtask.
For all subtasks: 2 ≤ K ≤ N ≤ 500 000.
Subtask 1 (14%): 2 ≤ K ≤ N ≤ 8.
Subtask 2 (15%): 2 ≤ K ≤ 50, 2 ≤ N ≤ 30 000.
Subtask 3 (17%): K = 2.
Subtask 4 (13%): K = N - 1.
Subtask 5 (10%): The optimal answer will have no more than 2 cats.
Subtask 6 (11%): An optimal solution exists such that no two cats start at the same time.
Subtask 7 (20%): No additional constraints.
Subtask 8 (0%): Sample Testcases.
Sample Input 1
1 2 1 2 3
Sample Output 1
1 0 1 0 0
Explanation for Sample 1
Peanut has two cats: one starting to shout at time 0, the other starting to shout at time 2. At time 2, 1 and 3 are being shouted by one cat each, so Peanut only hears 1. At all other times, there is only one cat shouting.
Sample Input 2
1 1 1 2
Sample Output 2
1 1 1 0
Sample Input 3
1 2 1 2 3 4 5 4 5 5
Sample Output 3
1 0 3 0 2 1 0 0 0 0