대기 시간

여러분은 유명한 놀이공원에 취직했다. 그곳에는 해결해야 할 흥미로운 문제가 많지만, 첫 임무는 롤러코스터를 타려고 줄을 선 사람들에게 제공되는 정보를 개선하는 것이다. 현재 그들이 가진 최선의 수단은 줄의 길이와 관계없이 ``여기서부터 대기 시간은 20분''이라고 적힌 표지판뿐이다.

유일한 롤러코스터 차량에는 $K$명이 탈 수 있으며, 한 바퀴를 도는 데 1분이 걸린다. 내리고 타는 데에는 시간이 들지 않는다. 방문객들은 여러 차량에 나뉘어 타는 것을 원하지 않는 그룹 단위로 줄에 합류한다. 따라서 다음 그룹이 너무 커서 차량이 완전히 차지 않는 경우가 때때로 발생한다. 이런 경우 놀이기구 직원들은 줄의 뒤쪽에 있는 어떤 그룹을 먼저 타게 하여 차량을 최대한 채운다. 예를 들어 현재 차량에 빈자리가 $x$개 있다면, 줄에서 크기가 $x$보다 작거나 같은 다음 그룹을 찾아 그 그룹으로 차량을 채운다. 그런 다음 더 이상 차량에 탈 수 있는 그룹이 없을 때까지 이 과정을 반복한다. 여러분의 임무는 줄에 있는 각 그룹이 얼마나 오래 기다려야 하는지 계산하는 것이다.

채점

제출한 풀이는 여러 테스트 그룹으로 테스트한다. 한 그룹의 점수를 얻으려면 그 그룹의 모든 테스트 케이스를 통과해야 한다.

그룹 | 점수 | 제한 조건

$1$ |$20$| $N \leq 1000$, $1 \leq K \leq N$

$2$ |$40$| $N \leq 10^5$

$3$ |$40$| 추가 제한 조건 없음.

첫째 줄에는 줄에 있는 그룹의 수와 차량 한 대에 탈 수 있는 사람 수를 나타내는 두 정수 $N$와 $K$가 주어진다 ($1 \leq N \leq 10^6$, $1 \leq K \leq 10^8$). 다음 줄에는 줄에 있는 그룹들의 크기를 나타내는 $N$개의 정수 $g_i$가 주어진다 ($1 \leq g_i \leq K$). 입력의 첫 번째 그룹이 줄의 맨 앞에 서 있는 그룹이다.

각 그룹의 대기 시간을 나타내는 $N$개의 정수를 공백으로 구분하여 한 줄에 출력한다.

세 그룹이 줄에 서 있고, 각 차량에는 정확히 세 명이 탈 수 있으며, 처음 줄의 상태가 $[2,2,1]$라고 하자. 먼저 첫 번째 그룹이 차량에 탈 차례가 된다. 이제 차량에는 자리가 하나 남으므로, 줄의 마지막 그룹인 한 명짜리 그룹이 다음 차례를 기다려야 하는 두 번째 그룹보다 먼저 타게 된다. 따라서 첫 번째 그룹과 마지막 그룹의 대기 시간은 0이고, 두 번째 그룹의 대기 시간은 1단위이다. 그러므로 0 1 0를 출력한다.