원형 서가의 책 바구니

문제

한 도서관의 어린이 자료실에는 N개의 낮은 서가가 원형으로 놓여 있다. 서가에는 원을 따라 1번부터 N번까지 번호가 붙어 있다. 각 서가 앞에는 책을 임시로 담는 바구니가 하나씩 있으며, 처음에 i번 바구니에는 A_i권의 책이 들어 있다. 도서관은 이용자가 여러 서가의 책을 살펴볼 수 있도록 바구니의 책 일부를 다음 서가로 옮기는 행사를 진행한다. 행사는 한 번만 진행한다. 각 서가의 담당자는 행사가 시작되는 순간 자기 바구니에 있는 책 중 최대 K권을 꺼낸다. 처음 책이 K권 이상이면 정확히 K권을 꺼내고, K권보다 적으면 있는 책을 모두 꺼낸다. 꺼낸 책은 다음 번호의 바구니에 넣으며, N번 바구니에서 꺼낸 책은 1번 바구니에 넣는다. K가 0이면 어느 바구니에서도 책을 꺼내지 않는다. 모든 담당자는 처음 상태를 기준으로 옮길 책의 수를 결정하고 동시에 이동을 수행한다. 다른 바구니에서 새로 받은 책을 이번 행사에서 다시 꺼내 보내지는 않는다. 예를 들어 처음 책이 없는 바구니는 행사 도중 책을 받더라도 다음 바구니로 보내는 책이 0권이다. 번호가 작은 바구니부터 계산하더라도 이 동시 이동 규칙을 지켜야 한다. 서가가 하나뿐이면 다음 바구니 역시 자기 자신이다. 이 경우 꺼낸 책이 같은 바구니로 돌아오므로 최종 책 수는 처음과 같다. 책의 종류와 순서는 고려하지 않으며 각 바구니에 남는 책의 수만 구한다. 처음의 책 수가 같은 바구니도 번호에 따라 따로 처리한다. 모든 이동이 끝난 뒤 1번부터 N번까지 각 바구니에 들어 있는 책의 수를 순서대로 출력한다.

입력

첫째 줄에 서가의 수 N과 한 바구니가 보낼 수 있는 최대 책 수 K가 공백으로 구분되어 주어진다. 1 ≤ N ≤ 100,000, 0 ≤ K ≤ 9이다.
둘째 줄에 A_1부터 A_N까지 공백으로 구분되어 주어진다. 0 ≤ A_i ≤ 9이다. 모든 수는 정수이다.

출력

이동이 모두 끝난 뒤 각 바구니의 책 수를 1번부터 N번까지 공백으로 구분하여 한 줄에 출력한다.

4 3
5 1 0 4

5 3 1 1

1 7
4

4

5 0
0 9 2 2 1

0 9 2 2 1

출처: Devin.KR 자체 제작