Math Problem Solver

Gifts (100 points)

Statement

You are hosting a party with n

guests but have prepared only m

gifts, where m<n

. To decide who should receive a gift, you assign each guest a tier number ti

(1≤ti≤109

). The lower the tier number, the closer the guest is to you. Guests with a tier number of 1

are your closest friends.

You will distribute the gifts based on the tier numbers:

First, give gifts to all guests in tier 1

.

Then, proceed to tier 2

, tier 3

, and so on.

If there are not enough gifts for all guests in a tier, prioritize guests based on their arrival order. For simplicity, guests arrive in the order of their indices; that is, guest i

arrives before guest j

if i<j

.

Determine which guests will receive a gift.

Input Format

The first line contains two integers n

and m

(1≤m<n≤105

) — the number of guests and the number of gifts.

The second line contains n

integers t1,t2,…,tn

(1≤ti≤109

) — the tier numbers of the guests.

Output Format

Output a single line containing n

integers x1,x2,…,xn

, where xi=1

if guest i

receives a gift, and xi=0

otherwise.

Sample Input

8 6

3 1 4 1 5 9 2 5

Sample Output

1 1 1 1 1 0 1 0

Explanation

Guests 2 and 4 are in tier 1

and both receive gifts.

Guest 7 is in tier 2

and receives a gift.

Guest 1 is in tier 3

and receives a gift.

Guest 3 is in tier 4

and receives a gift.

Guest 5 and 8 is in tier 5

but there is only one gift left. Since 5<9

, Guest 5 receives a gift but not Guest 8.

Guest 6 is in tier 9

and does not receive a gift.

Constraints

1≤m<n≤105

,