Pirate Gold Distribution

There are n pirates (numbered 1 through n) with strictly positive greed coefficients a_i (an integer) for pirate i. The pirates are ranked by their numbers: a lower number means higher status.

The pirates have m gold coins to distribute. The distribution procedure is as follows:

1. The pirate with the smallest number who is still on board (i.e. not thrown overboard) proposes a plan. In the plan, every pirate still on board receives b_i coins, with \(\sum b_i = m\).
2. Then every pirate on board (including the proposer) votes for or against the proposal.
   • If at least 50% of the pirates vote in favor (that is, yes votes \(\ge\) 50%), the coins are allocated according to the proposal.
   • Otherwise, the proposer is thrown overboard (and gets no coins), and the process is repeated with the remaining pirates.

For each pirate i, his voting rule is as follows. Let \(d_i\) be the number of coins he would eventually receive if the current proposal is rejected. (Note that if by rejecting the proposal a pirate would eventually be thrown overboard, then he is considered to eventually receive 0 coins.) Pirate i will vote for the proposal if and only if at least one of the following holds:

• If he would eventually be thrown overboard by rejecting the plan.
• His share in the proposal satisfies \(b_i \ge d_i + a_i\). (Here the extra \(a_i\) is his greed coefficient.)

All pirates know every other pirate's greed coefficient and all follow fixed strategies. When it is a pirate's turn to propose a plan, he behaves as follows:

1. If no proposal exists in which he can avoid being thrown overboard, then he proposes to take all m coins for himself (and 0 for everyone else), accepting that his proposal will be rejected and that he will be thrown overboard.
2. Otherwise, he chooses one acceptable proposal that maximizes his own coin share \(b_i\). Among all acceptable proposals that maximize his own gain, he then chooses one that minimizes the share of pirate \(i+1\); if there is still a tie, he minimizes the share of pirate \(i+2\), and so on.

Your task is to determine the final number of coins each pirate receives.

Note on the voting: In a proposal, if a pirate who is not bribed receives 0 coins while he would have received more if the current proposal were rejected, he will vote against even if his vote is not needed for a simple 50% majority. Nevertheless, the proposal is accepted if at least 50% of pirates vote yes.

---

Formal specifications:

Let the current set of pirates be \(\{i,i+1,\dots,n\}\) and let the number of pirates be \(r=n-i+1\). Define the quorum \(L = \lceil r/2 \rceil\). For each pirate \(j>i\) the cost to buy his vote is defined as follows:

[ cost_j = \begin{cases} d_j + a_j, & \text{if pirate (j) survives in the outcome if the proposal is rejected}\ 0, & \text{if pirate (j) would be thrown overboard (so that rejecting is fatal)} \end{cases} ]

To get his proposal accepted, pirate \(i\) needs at least \(L-1\) additional "yes" votes (his own vote already counts). He can "buy" a vote by offering pirate \(j\) exactly \(cost_j\) coins (so that \(b_j = cost_j\)). The remaining pirates not bribed are offered \(b_j = 0\). If fewer than \(L-1\) bribery is needed because some pirates automatically vote yes (i.e. their \(cost_j=0\)), then no extra coins are given. In the proposal the proposer takes \(m - \sum_{j \text{ bribed}} cost_j\) coins.

If the coins available are insufficient to pay for the votes required, then no acceptable proposal exists and the pirate proposing will be thrown overboard. In that case his final coin count is 0.

inputFormat

The first line contains two integers n and m (1 ≤ n ≤ 100, 1 ≤ m ≤ 109), which denote the number of pirates and the total coins respectively.

The second line contains n positive integers a₁, a₂, ..., a_n (1 ≤ ai ≤ 109), where a_i is the greed coefficient of pirate i.

outputFormat

Output n integers in one line separated by a space, where the i-th integer is the number of coins that pirate i finally receives. (A pirate who is thrown overboard is considered to receive 0 coins.)

sample

1 10
5

10

</p>