T University boasts countless excellent student organizations, such as the Students' Association of Acid with 118 core members, the Students' Association of Bamboo Basket which garnered significant attention immediately upon its founding, and, of course, the world-renowned Students' Association of Garlic. At the beginning of each semester, T University holds a university-wide club recruitment event. Due to its massive scale, this event is known as the "Hundred Clubs War." Allocating the limited space to various clubs, much like the Hilbert Hotel, is always the most headache-inducing problem for the organizers. This year, the organizers were impressed by the Garlic Association's ability to cleanly dismantle a whole head of garlic into cloves, so they approached the Garlic Association, hoping to use "garlic algorithms" to solve the booth allocation problem.

Specifically, there are $T$ clubs this year that wish to participate in the Hundred Clubs War, and the space available for the clubs can be viewed as $H$ slots arranged in a straight line along Xuetang Road. To encourage healthy competition among clubs, the organizers decided to allocate space based on each club's contribution to the university in the previous academic year. In the order of their application submissions, the contribution of the $i$-th club to T University in the previous academic year is $u_i$. The organizers hope to allocate all $H$ slots to the clubs according to the following rules:

• For each club, calculate the sequence $u_i, u_i/2, u_i/4, \cdots, u_i/2^{H-1}$.
• From the $T \times H$ values calculated, repeatedly remove the largest one and assign a slot to the corresponding club's booth until all $H$ slots have been allocated. If there are multiple maximum values:
  • If there are clubs that have not yet been assigned any slots, prioritize those clubs. Otherwise, prioritize the club with the largest original $u_i$.
  • If there are still multiple clubs that can be assigned, allocate to them in the order of their application submissions.

Since most members of the Garlic Association have gone to plant garlic for the winter, you, who are currently mincing garlic in the Cooking and Alchemy Department, are asked to assist the organizers in calculating how many slots each club will receive.

Input

The first line of input contains two positive integers $T$ ($1 \le T \le 10^5$) and $H$ ($1 \le H \le 10^9$), representing the number of clubs and the number of slots, respectively.

The second line contains $T$ positive integers $u_1, u_2, \cdots, u_T$ ($1 \le u_i \le 10^9$), representing the contribution of each club.

Output

Output a single line containing $T$ integers, where the $i$-th ($1 \le i \le T$) integer represents the number of slots allocated to the $i$-th club.

Examples

Input 1

4 7
2 1 4 3

Output 1

1 1 3 2

Input 2

9 27
801 919 210 101 417 713 304 613 921

Output 2

4 4 2 1 3 4 2 3 4