After a voyage lasting many months and full of failures, the pirates of the ship Floating Point accidentally discovered a treasure consisting of $m$ identical gold coins. They decided to divide the treasure and end the voyage.

During the voyage, the pirates got to know each other. They all know that every pirate thinks perfectly logically (many of them started their pirate careers by cracking software security) and that they are primarily driven by greed, although some pirates are greedier than others. A linear hierarchy has also been clearly established – the pirates are numbered from $1$ to $n$.

To divide the treasure, the pirates use a traditional pirate technique. The pirate with the lowest number (among those not yet thrown overboard) proposes a division of the treasure, i.e., for each pirate $i$ not yet thrown overboard, they specify $b_i$, a non-negative integer number of gold coins that this pirate will receive in the proposed division (the sum of all values $b_i$ is $m$). Then, all pirates (including the proposer) vote for or against the proposed division. If at least 50% of the pirates vote for the division, the treasure is distributed according to the proposal. Otherwise, the pirate making the proposal is thrown overboard and does not participate in further negotiations, nor do they receive any gold coins. Then, this procedure is repeated (the next pirate in the hierarchy proposes a division to the remaining pirates).

Each pirate $i$ votes for the proposed division if, in the event of the proposal being rejected: they would be thrown overboard after proposing their own division, or $b_i \geq d_i + a_i$, where $d_i$ is the number of coins the pirate would get after the proposal is rejected, and $a_i$ is their greed coefficient.

All pirates know all the greed coefficients and know that everyone will follow this deterministic strategy in their choices: If there is no acceptable division (i.e., one that would be accepted by at least half of the pirates not yet thrown overboard), the pirate proposes that they take the entire treasure themselves. Then, resigned to their fate, they allow themselves to be thrown overboard. If an acceptable division exists, one of such divisions will be proposed (it is better to receive even 0 coins than to be thrown overboard). Among many possible acceptable proposals, the pirate chooses the division in which they keep the largest part of the treasure for themselves. Pirates are inclined to blame pirates closer in the hierarchy for previous failures, so if the division is still not unique, they prefer to allocate more coins to pirates with a higher number. Specifically: pirate $i$, when choosing among the still available acceptable divisions, minimizes in order: the number of coins received by pirate $i+1$, then the number of coins received by pirate $i+2$, and so on.

Your task is to write a program that determines how many gold coins each pirate will receive, according to the above rules.

Input

The first line contains two integers $n$ and $m$ ($1 \leq n \leq 50\,000$, $1 \leq m \leq 5\,000\,000$) denoting the number of pirates and the number of gold coins to be divided, respectively.

The second line contains a sequence of $n$ integers $a_1, a_2, \dots, a_n$ ($1 \leq a_i \leq 64$), denoting the greed coefficients of the successive pirates.

Output

The output should contain one line with $n$ integers $b_1, b_2, \dots, b_n$. If the $i$-th pirate is thrown overboard after applying the procedure described in the problem, then $b_i = -1$; otherwise, $b_i$ denotes the number of coins the $i$-th pirate receives.

Examples

Input 1

3 100
28 1 56

Output 1

44 0 56

Input 2

5 1
1 1 1 1 1

Output 2

-1 0 0 1 0

Input 3

6 6
3 5 1 4 2 6

Output 3

2 0 0 0 4 0

Note

In the first example, we have three pirates: Algor, Bajtazar, and Char. If Algor were thrown overboard, Bajtazar would make a division in which he receives all 100 coins, and Char receives nothing. Although Char would not accept such a solution, he would be outvoted by Bajtazar.

Therefore, Algor is in no way able to convince Bajtazar to vote in favor (he would have to offer him at least $100 + 1$ coins). Thus, he needs to convince Char by giving him enough coins (specifically at least $0 + 56$). Consequently, Algor offers 56 coins to Char and keeps 44 coins for himself – Algor and Char will vote for such a division, outvoting Bajtazar.

In the second example, the first pirate has too few gold coins to divide to satisfy enough pirates. He therefore proposes that he takes a coin for himself, after which he is thrown overboard. The second pirate has two divisions to choose from that are accepted. He can give a coin to the third or the fourth pirate – according to the rules, he chooses the latter division.

In the third example, the pirates numbered 1, 2, and 5 voted for the division proposed by the first pirate.