Банк#483

Банк

1 секунда
256 мегабайтів
Дуже складна

Містер IP витратив багато грошей цього місяця — він заплатив разів своєю банківською карткою, і -та оплата коштувала йому точно 2^{a_i} грн.

Тепер його банківський додаток згрупував його витрати за категоріями (наприклад, ресторани, продукти, таксі, ігри тощо). Всього є категорій.

Однак його бос буде дуже сердитий, якщо дізнається, що містер IP витратив занадто багато грошей на будь-яку конкретну категорію. На щастя, ви знайшли вразливість у додатку, яка дозволяє вам редагувати категорію будь-якої оплати.

Тепер ви хочете використати це, щоб допомогти містеру IP зробити найбільшу суму витрат для однієї категорії якомога меншою серед усіх категорій. Іншими словами, якщо після внесення змін сума витрат для -ї категорії дорівнює s_i, ви хочете мінімізувати значення \max_{i=1}^k s_i.

Містер IP боїться свого боса і просить вас допомогти йому. Він хоче, щоб ви вивели цілих чисел c_1, c_2, \dots, c_n, де 1 \le c_i \le k позначає номер категорії, до якої ви призначили -ту оплату.

Вхідні дані

Перший рядок містить два цілі числа і (1 \le k \le n \le 2 \cdot 10^5) — кількість оплат та кількість категорій.

Другий рядок містить цілих чисел a_1, a_2, \dots, a_n (0 \le a_i < n).

Вихідні дані

Виведіть цілих чисел  — значення c_1, c_2, \dots, c_n (1 \le c_i \le k), що дають призначення категорій для оплат, яке мінімізує найбільшу суму витрат для однієї й тієї ж категорії.

Приклади

Приклад 1

Loading
Loading

Приклад 2

Loading
Loading

Приклад 3

Loading
Loading

Примітка

У першому тесті витрати становлять \{2^3, 2^2, 2^1, 2^0\} = \{8, 4, 2, 1\} грн. Розділивши їх на дві групи і \{4, 2, 1\}, ми можемо досягти найбільших витрат для однієї групи, що становитиме . Ми можемо показати, що зробити краще неможливо.

У другому тесті один зі способів досягнення відповіді полягає в розподілі витрат на \{2^1, 2^1, 2^1\},\ \{2^1, 2^1, 2^1\},\ \{2^1, 2^1\}, при цьому найбільша сума витрат для однієї категорії становитиме 2+2+2=6. Ми можемо показати, що зробити краще неможливо.

У третьому тесті, незалежно від того, як ми групуємо витрати, одна категорія завжди міститиме елемент 2^5 = 32, отже, одне можливе призначення це \{2^5\},\ \{2^1, 2^1, 2^1, 2^1, 2^1, 2^1\},\ \{\}, що досягає найменшої можливої відповіді .

Оцінювання

У кожному блоці тести оцінюються незалежно.

  1. ( балів): a_i < 30;

  2. ( балів): без додаткових обмежень.