채팅

가끔은 오랜 친구와 함께 겪어 온 모든 일을 떠올릴 때가 있다. 다행히도 소셜 네트워크는 모든 메시지 기록을 저장하므로 10년 전에 무엇을 두고 다퉜는지 쉽게 알 수 있다.

보다 형식적으로 말하면, 메시지 기록은 전송 시간순으로 정렬되고 1부터 n까지 번호가 매겨진 메시지의 수열이며, 여기서 n은 채팅에 있는 메시지의 총개수이다.

각 메시지에는 자신이 답장한 이전 메시지로 연결되는 링크가 있을 수 있다. 메시지 x를 열거나 그 메시지로 연결되는 링크를 따라가면, 메시지 x를 기준으로 이전 메시지 k개, 메시지 x, 다음 메시지 k개가 보이도록 대화가 표시된다. 어느 한쪽에 메시지가 k개보다 적은 경우에도 존재하는 메시지는 모두 표시된다.

메시지 기록을 깊이 살펴볼 때, 항상 보이는 모든 메시지를 읽은 다음 현재 메시지 x에 있는 링크가 있다면 그 링크를 따라가고, 같은 방식으로 계속 읽는다.

1부터 n까지의 모든 t에 대해 메시지 번호 t에서 시작할 경우 읽게 되는 메시지의 개수를 구한다. 각 수는 독립적으로 계산한다. 메시지 x에서 시작하면 초기 화면에는 x 자체와 이전 메시지 k개, 다음 메시지 k개가 표시된다. 여러 번 읽은 메시지는 하나로 간주한다.

첫째 줄에 채팅에 있는 메시지의 총개수와 보이는 이전 및 다음 메시지의 개수를 나타내는 두 정수 n과 k (1 ≤ n ≤ 105, 0 ≤ k ≤ n)이 주어진다.

둘째 줄에 정수의 수열 a1, a2, ..., an (0 ≤ ai < i)이 주어진다. 여기서 ai는 i-th 메시지의 링크가 가리키는 목적지를 나타내며, i에서 나가는 링크가 없으면 zero이다. 모든 메시지는 시간순으로 나열된다. 메시지 x의 링크는 반드시 번호가 x보다 엄격히 작은 메시지를 가리킨다.

n개의 정수를 출력한다. 이때 i-th 정수는 메시지 i에서 시작하여 가능한 동안 링크를 따라갔을 때 읽을 수 있는 서로 다른 메시지의 개수를 나타낸다.

첫 번째 예제에서 i = 6인 경우를 생각해 보자. 메시지 6을 읽고, 이어서 2, 그다음 1을 읽으며, 이후에는 따라갈 링크가 없다.

두 번째 예제에서는 i = 6일 때 k = 1이므로 메시지 5, 6, 7을 읽고, 이어서 4, 5, 6을 읽은 다음 2, 3, 4를 읽으며, 이후 링크 수열이 끊어진다. 여기서 서로 다른 메시지의 개수는 6이다.