Г-н Хобсон ушел из управления конюшней и вложил средства в более современный вид транспорта — поезда. Он построил железнодорожную сеть из n станций. Однако он сохранил свою приверженность к освобождению пассажира от бремени слишком большого выбора: с каждой станции пассажир может сесть на поезд ровно до одной другой станции. Такое путешествие называется этап. Обратите внимание, что это путешествие в один конец, и вернуться обратно может не быть возможности.
Хобсон также предлагает ровно один вариант билета, который позволяет пассажиру проехать до k этапов за одну поездку. На выходе с каждой станции стоит автоматизированный считыватель билетов (только один, чтобы пассажирам не приходилось решать, каким воспользоваться). Автомат проверяет, что расстояние от начальной станции до конечной не превышает k этапов.
Каждый считыватель билетов должен быть запрограммирован списком допустимых стартовых станций. Однако чем больше памяти потребуется для этого списка, тем дороже будет машина. Помогите Хобсону, определив для каждой станции A количество станций (включая A), с которых клиент может добраться до A не более чем за k этапов.
Рисунок H.1: Иллюстрация к примеру 1. Каждый кружок представляет станцию. Числа вне кружков — это номера станций, загруженные в считыватели билетов при k=2.
В первой строке записаны два целых числа n и k, где n (2≤n≤5⋅105) — количество станций, а k (1≤k≤n−1) — максимальное количество этапов, которое можно проехать по билету. Далее следуют n строк, i-я из которых содержит целое число di (1≤di≤n и di=i) — станцию, до которой можно добраться со станции i на одном участке.
Выведите n строк. В i-й строке выведите количество станций, с которых можно добраться до станции i не более чем за k этапов.