Fast Forward

Interview

Time limit2sMemory limit1024 MB

Summary

For each start song in a circular playlist, count the ads that play when an ad can only follow a song and at least c seconds must pass between ads.

Level: Medium6 of 10
Topics: Prefix sum, Greedy, Binary search, Array
Solved: No attempts yet

Problem

Gry has started to use the new Expify song streaming platform. Gry does not want to spend money, so Expify forces him to listen to advertisements. An advertisement can be played only after a song ends (it cannot be played in the middle of a song), and only if at least $c$ seconds have passed since the previous advertisement ended.

Gry has a circular playlist with $n$ songs. The duration of the $i$ -th song is $d_i$ seconds. Gry wants to minimize the number of advertisements, so he wants to know how many advertisements will play if he starts listening to the whole playlist from the $i$ -th song. The playlist stops after $n$ songs, wrapping around the circle as needed.

An advertisement plays right before Gry starts listening. That advertisement and the one that plays after the playlist stops are not counted.

Input

The first line contains $n$ and $c$ ( $1 \leq n \leq 10^6$ , $1 \leq c \leq 10^9$ ). The second line contains the $n$ song durations $d_1, d_2, \ldots, d_n$ ( $1 \leq d_i \leq 10^3$ ).

Output

For each starting song $i$ from 1 to $n$ , print the number of advertisements when Gry starts from the $i$ -th song. Print the $n$ answers on one line, separated by spaces.

Examples2

Example 1
Input
```
7 7
1 1 1 1 1 1 1
```
Expected output
```
0 0 0 0 0 0 0
```
Example 2
Input
```
3 3
1 1 3
```
Expected output
```
0 1 1
```