Задача G. Grading ≡

Условие

В классе учится N человек. Для удобства будем нумеровать их от 1 до N.

Однажды учитель по информатике дал очень сложную контрольную работу. Естественно, есть люди, которые ее спишут, а есть люди, которые будут делать ее сами и получат максимальную оценку (в школе K-бальная система оценивания, то есть ученик может получить оценку, которая равна натуральному числу на промежутке от 1 до K). Но если человек с номером U спишет у человека с номером V, и у человека V балл равен X, то у человека U балл будет равен X − 1 (если X = 1, то человек получит оценку 1, так как оценки меньше нет).

На контрольную давалось не очень много времени, из-за этого могло получиться так, что первый ученик списал у второго, второй списал у третьего, ..., T-ый списал у первого. В таком случае у всех школьников оставались пустые листы ответов, а следовательно, они получили оценку 1.

Вам известно, кто у кого списывал. Помогите классу и скажите, кто какую оценку получит!

Формат входных данных

В первой строке вводятся натуральные числа N и K — количество учеников и число системы оценивания. В следующей строке находится последовательность A из N натуральных чисел, i-ое число означает то, что i-ый школьник списал у A_i-ого.

Формат выходных данных

В единственной строке выведите N чисел, где i-ое число показывает, какую оценку получил i-ый школьник.

Ограничения

1 ≤ K ≤ N ≤ 10⁵, 1 ≤ A_i ≤ N

Пояснение к примеру

Первый списал у второго, второй списал у четвертого, четвертый списал у первого. Эти 3 ученика получили оценку 1. Третий сделал работу сам и получил оценку 3, пятый списал работу у третьего и получил 2.

Примеры тестов

5 3
2 4 3 1 3

1 1 3 1 2