Problem 0G. Grading ≡

Statement

In the class, there are N students, conveniently numbered from 1 to N.

One day, the computer science teacher gave a very challenging test. Naturally, some students will copy it, while others will attempt it independently and receive the maximum score (the school uses a K-point grading system, meaning a student can receive a grade as a natural number in the range from 1 to K). However, if student U copies from student V, and student V's score is X, then student U's score will be X − 1 (if X = 1, then the student will receive a grade of 1, as there is no lower grade).

Due to the limited time for the test, it could happen that the first student copied from the second, the second copied from the third, ..., the T-th copied from the first. In this case, all students would have empty answer sheets, and therefore, they would receive a grade of 1.

You know who copied from whom. Help the class and determine the grade each student will receive!

Input format

The first line contains natural numbers N и K — the number of students and the grading system value. The next line contains a sequence A of N natural numbers, where the i-th number indicates that the i-th student copied from the A_i-th student.

Output format

In a single line, output N numbers, where the i-th number indicates the grade received by the i-th student.

Constraints

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

Example explanation

The first student copied from the second, the second copied from the fourth, the fourth copied from the first. These three students received a grade of 1. The third student did the work independently and received a grade of 3, while the fifth copied the work from the third and received a grade of 2.

Sample tests

5 3
2 4 3 1 3

1 1 3 1 2

Explanation

Давайте создадим ориентированный граф из N вершин, проведем ребро из вершины V в вершину U, если U-ый ученик списал у V-ого. Если U = V, то есть ученик выполнял работу сам, то просто не будем проводить ребро.

Запустим поиск в глубину из вершин, которые принадлежат ученикам, которые работу выполняли сами, попутно вычисляя оценку каждого ученика (которая равна максимуму из 1 и оценки ученика, у которого списал человек, уменьшенной на единицу). Докажем, что из этих вершин не достижим цикл.

Допустим, это не так. Тогда в каждой компоненте связности, в которой есть ученик, делавший работу сам, есть хотя бы N ребер (в каждую вершину, кроме двух, входит по одному ребру, в вершину того, кто решал сам, не входит ребер совсем, и еще в одну вершину входит два ребра, итого N ребер). А это значит, что в графе есть цикл. Получили противоречие.

Итак, рассмотрим все остальные вершины, оценки которых мы еще не вычислили. Заметим, что все остальные вершины либо лежат на цикле, либо достижимы из вершин цикла. А это значит, что все оставшиеся вершины получили оценку 1.