Roller Coaster

Interview

Time limit2sMemory limit1024 MB

Summary

Given N groups of sizes a_i and a coaster that holds M people, print the earliest ride index (starting from 0) each group can board, keeping group order.

Level: Easy3 of 10
Topics: Simulation, Greedy
Solved: No attempts yet

Problem

In Japan Amusement Group (JAG), members discuss how to make attractions more appealing so that many people come. Lately they have been interested in reducing the stress of waiting in line. A member of JAG found a hypothesis that knowing the waiting time reduces this stress. You will write a program that predicts the waiting time for a roller coaster.

$N$ groups stand in line for the roller coaster. The groups are numbered from $1$ to $N$ , and group $i$ has $a_i$ people. People in line ride in ascending order of group number.

The first ride departs at time 0, and a ride departs every minute after that. The roller coaster holds up to $M$ people.

All members of a group must ride at the same time. A group does not need the car to be filled to exactly $M$ people. Each group wants to ride as early as possible, so a group rides as soon as it can.

Input

The first line contains two integers $N$ and $M$ , where $1 \le N \le 100\,000$ and $1 \le M \le 10^9$ . $N$ is the number of groups and $M$ is the capacity of the roller coaster.

The second line contains $N$ integers $a_1, a_2, \dots, a_N$ , where $1 \le a_i \le M$ .

Output

Print $N$ lines. The $i$ -th line contains the time at which group $i$ can ride the roller coaster.

Examples2

Example 1
Input
```
3 5
2 4 1
```
Expected output
```
0
1
1
```
Example 2
Input
```
2 1000000000
1000000000 1000000000
```
Expected output
```
0
1
```