B. Переписка с другом
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Иногда вспоминаешь старого друга и начинаешь вспоминать все, что с ним связано. Хорошо, что есть социальные сети: они хранят вашу переписку с самого знакомства, и можно с легкостью прочитать, о чем же вы спорили 10 лет назад.

Формально, ваша переписка — упорядоченная по времени последовательность сообщений, пронумерованных от 1 до n, где n — общее количество сообщений в переписке.

Каждое сообщение может содержать ссылку на более раннее сообщение, на которое оно является ответом. При открытии сообщения с номером x или при переходе по ссылке на сообщение с номером x диалог показывается так, что видны k сообщений до этого сообщения, само сообщение x и k сообщений после этого сообщения. Если до или после текущего сообщения было менее k сообщений, то все они отображаются.

Изучая старую переписку, вы всегда читаете все сообщения, показанные на экране, а затем переходите по ссылке в текущем сообщении x (в которое пришли по ссылке), если такая есть, и читаете дальше.

Определите количество различных сообщений, которые вы прочтете, если начинать читать переписку, открыв диалог на сообщении t, для каждого t от 1 до n. Считайте ответ для каждого случая независимо. Если начинать читать с сообщения номер x, то на экране изначально показаны k сообщений до сообщения x, само сообщение x и k сообщений после. Сообщения, прочитанные несколько раз, считаются за одно.

Входные данные

В первой строке следуют два целых числа n и k (1 ≤ n ≤ 105, 0 ≤ k ≤ n) — количество сообщений в переписке и количество сообщений, которые видны сверху и снизу от текущего.

Во второй строке следует последовательность целых чисел a1, a2, ..., an (0 ≤ ai < i), где ai равно нулю, если из сообщения i нет ссылки в предыдущее сообщение, либо ai равно номеру сообщения, в которое можно перейти по ссылке из сообщения i. Все сообщения перечислены в хронологическом порядке. Гарантируется, что если в сообщении с номером x есть ссылка, то она ведёт в сообщение с номером меньшим, чем x.

Выходные данные

Выведите n целых чисел, где i-е число должно быть равно количеству различных сообщений, которые можно прочитать, если начинать читать с i-го сообщения и переходить по ссылкам до тех пор, пока это возможно.

Примеры
Входные данные
6 0
0 1 1 2 3 2
Выходные данные
1 2 2 3 3 3
Входные данные
10 1
0 1 0 3 4 5 2 3 7 0
Выходные данные
2 3 3 4 5 6 6 6 8 2
Входные данные
2 2
0 1
Выходные данные
2 2
Примечание

Если начинать с шестого сообщения в первом примере, то вы прочитаете шестое сообщение, затем второе, затем первое и закончите, т. к. из первого сообщения нет ссылки.

Если начинать с шестого сообщения во втором примере, то вы сначала прочтете пятое, шестое и седьмое сообщение, затем перейдете по ссылке в пятое сообщение и прочтете четвертое, пятое и шестое сообщение, затем перейдете по ссылке в четвертое сообщение и прочитаете третье, четвертое и пятое сообщение, наконец, перейдете по ссылке в третье сообщение и прочитаете второе, третье и четвертое сообщение. Больше переходить по ссылкам вы не будете, так как из третьего сообщения ссылки нет. Итого вы прочтете все сообщения со второго по седьмое, таких шесть.