Problem G. Grading

Author:Евгений Татаринов   Time limit:1 sec
Input file:Standard input   Memory limit:256 Mb
Output file:Standard output  

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 Ai-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 ≤ 105, 1 ≤ Ai ≤ 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

No. Standard input Standard output
1
5 3
2 4 3 1 3
1 1 3 1 2

0.091s 0.018s 13