B. Binary Bracket
time limit per test
0.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

At the 2023 Wimbledon Championships, world No. 42 Marketa Vondrousova won the Ladies' Singles title, becoming the first ever unseeded competitor to do so. On her way to winning the title, she caused upsets against seeds Veronika Kudermetova, Donna Vekic, Marie Bouzkova, Jessica Pegula, and finally Ons Jabeur in the final.

As a tennis fan, Bob notices the high number of upsets in the Ladies' Singles bracket in the championships this year and wonders if this has anything to do with Vondrousova winning the title. He comes up with the following scenario:

Let there be a single elimination tournament with $$$2^K$$$ competitors, each player having a "power index" $$$P_i$$$. The tournament consists of $$$K$$$ rounds, and there are $$$2^{K-i}$$$ matches in the $$$i$$$-th round (The formal proceedings of the tournament is stated below). Each match has one winner (draws do not occur) who moves on to the next round, and the loser is eliminated from the tournament. We define a match as an "upset" if $$$P_{\text{winner}} \lt P_{\text{loser}}-X$$$ where $$$X$$$ is a constant given to you.

Formally, the tournament consists of $$$2^K-1$$$ matches. They are held as follows: the players are enumerated from $$$1$$$ to $$$2^K$$$, initially in input order, then split into pairs: player number $$$1$$$ plays against player number $$$2$$$, player number $$$3$$$ plays against player number $$$4$$$ (exactly in this order), and so on (so, $$$2^{K-1}$$$ games are played in this round). When a player loses a game, they are eliminated.

After that, only $$$2^{K-1}$$$ players remain. If only one player remains, they are declared the champion; otherwise, $$$2^{K-2}$$$ games are played in the next round: in the first one of them, the winner of the game "player $$$1$$$ vs player $$$2$$$" plays against the winner of the game "player $$$3$$$ vs player $$$4$$$", then the winner of the game "player $$$5$$$ vs player $$$6$$$" plays against the winner of the game "player $$$7$$$ vs player $$$8$$$", and so on.

This process repeats until only one player remains.

Bob now wonders, for each of the $$$2^K$$$ competitors, what is the minimum number of upsets in total (of the $$$2^K-1$$$ matches) for that competitor to become the champion?

Input

The input consists of two lines.

The first line consists of 2 integers $$$K$$$ ($$$1\le K\le 18$$$) and $$$X$$$ ($$$0\le X\le 10^9$$$).

The second line consists of $$$2^K$$$ integers $$$P_1$$$ to $$$P_{2^K}$$$, representing the power indices of the competitors. ($$$1\le P_i\le 10^9$$$).

Output

Output $$$2^K$$$ integers on a line, one for each player, the minimum number of total upsets in order for them to win the tournament.

Examples
Input
2 1
1 3 2 4
Output
2 0 1 0
Input
3 2
4 3 1 6 2 1 6 5
Output
0 1 2 0 1 2 0 0