Поїзди Гобсона

Г-н Хобсон вирішив залишити управління стайнею та інвестувати в сучасніший вид транспорту — поїзди. Він створив залізничну мережу з $n$ станцій. Проте, щоб зберегти свою відданість звільненню пасажирів від надмірного вибору, з кожної станції можна сісти на поїзд лише до однієї іншої станції. Таку подорож називають етапом. Зверніть увагу, що це подорож в один кінець, і повернення може бути неможливим.

Хобсон пропонує лише один вид квитка, який дозволяє пасажиру здійснити до $k$ етапів за одну поїздку. На виході з кожної станції встановлено автоматизований зчитувач квитків (лише один, щоб пасажири не мали вибору). Автомат перевіряє, що відстань від початкової станції до кінцевої не перевищує $k$ етапів.

Кожен зчитувач квитків має бути запрограмований списком допустимих стартових станцій. Однак, чим більше пам'яті потрібно для цього списку, тим дорожче буде машина. Допоможіть Хобсону, визначивши для кожної станції $A$ кількість станцій (включаючи $A$), з яких можна дістатися до $A$ не більше ніж за $k$ етапів.

Рисунок H.1: Ілюстрація до прикладу 1. Кожне коло представляє станцію. Числа поза колами — це номери станцій, завантажені в зчитувачі квитків при $k=2$.

Вхідні дані

У першому рядку записані два цілих числа $n$ і $k$, де $n(2\le n\le 5\cdot 10^5)$ — кількість станцій, а $k(1\le k\le n-1)$ — максимальна кількість етапів, яку можна проїхати за квитком. Далі слідують $n$ рядків, $i$-й з яких містить ціле число $d_i(1\le d_i\le n$ і $d_i\ne i)$ — станцію, до якої можна дістатися зі станції $i$ на одному етапі.

Вихідні дані

Виведіть $n$ рядків. У $i$-му рядку виведіть кількість станцій, з яких можна дістатися до станції $i$ не більше ніж за $k$ етапів.

Приклади