E. Powerhouse of the Cell?
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Jasmine has recently learned that the mitochondria are the powerhouse of the cell and produce ATP, which is the energy currency of your body. Since Jasmine is healthy and fit, her mitochondria produce $$$m$$$ ATP each day.

Jasmine has to do $$$n$$$ tasks today, numbered from $$$1$$$ to $$$n$$$ from highest to lowest priority. The $$$i$$$-th task costs $$$a_i$$$ ATP. Since some tasks have higher priority than others, Jasmine will choose some integer $$$k$$$ and only consider doing the $$$k$$$ tasks with the highest priority. Out of the tasks she considers, she tries to complete the most possible tasks. Jasmine cannot do the same task more than once.

For each $$$k$$$ from $$$1$$$ to $$$n$$$, find the maximum number of tasks that Jasmine could complete if she only considers the $$$k$$$ tasks with the highest priority.

Input

The first line of the input will contain two integers $$$n$$$ and $$$m$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$, $$$1 \leq m \leq 10^9$$$).

The second line of the input will contain $$$n$$$ integers $$$a_1 \dots a_n$$$ ($$$1 \leq a_i \leq 10^9$$$).

Output

For each $$$k$$$ from $$$1$$$ to $$$n$$$, print the maximum number of tasks that Jasmine can complete with $$$m$$$ ATP if she only considers the first $$$k$$$ tasks.

Example
Input
5 15
14 15 11 4 4
Output
1
1
1
2
2