Mister IP spent a lot of money this month — he paid times with his bank card, and the -th payment costs him exactly 2^{a_i} UAH.
Now, his bank application grouped his spendings into categories (e.g. restaurants, groceries, taxi, games, etc.). In total, there are categories.
However, his Boss will be very angry if he finds out that Mister IP spent too much money for any particular category. Luckily, you've found a vulnerability in the application which allows you to edit the category of any payment.
Now you want to use it to help Mister IP make the largest amount of money spent for one category as small as possible across all categories. In other words, if after making the edits, the amount of money spent for the -th category is s_i, you want to minimize the value of \max_{i=1}^k s_i.
Mister IP is afraid of his Boss and asks you to help him. He wants you to output integers c_1, c_2, \dots, c_n, where 1 \le c_i \le k denotes the number of the category you've assigned the -th payment to.
The first line contains two integers and (1 \le k \le n \le 2 \cdot 10^5) — the number of payments, and the number of categories.
The second line contains integers a_1, a_2, \dots, a_n (0 \le a_i < n).
Output integers — the values c_1, c_2, \dots, c_n (1 \le c_i \le k) giving the assignment of categories for the payments that minimizes the largest amount of money spent for the same category.
Example 1
Example 2
Example 3
In the first test, the spendings are \{2^3, 2^2, 2^1, 2^0\} = \{8, 4, 2, 1\} UAH. By splitting them into two groups and \{4, 2, 1\}, we can achieve the largest spent money for one group to be . We can show that it's impossible to do better.
In the second test, one way of achieving the answer is splitting the spendings into \{2^1, 2^1, 2^1\},\ \{2^1, 2^1, 2^1\},\ \{2^1, 2^1\} with the largest amount of money spent for the same category being 2+2+2=6. We can show that it's impossible to do better.
In the third test, no matter how we group the spending, one category will always contain the element 2^5 = 32, hence one possible assignment is \{2^5\},\ \{2^1, 2^1, 2^1, 2^1, 2^1, 2^1\},\ \{\} achieving the smallest possible answer .
In each block, the tests are evaluated independently.
( points): a_i < 30;
( points): no additional restrictions.