Пінгвіни#495

Пінгвіни

1 секунда
256 мегабайтів
Середня

Містер ІП має плюшевого пінгвіна, тому пінгвіни з Байтеланду попросили його про допомогу. Є родин пінгвінів; -та родина має 1 \le a_i \le 3 пінгвінів.

Вони хочуть побудувати міст і просять Містера ІП розділити їх на команд для цього. Звичайно, всі пінгвіни з однієї родини повинні бути в одній команді, а команди повинні мати якомога схожі розміри. Іншими словами, ви повинні розділити родини на команд так, щоб різниця між найбільшою та найменшою командами була мінімізована.

Вхідні дані

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

Другий рядок містить цілих чисел a_1, a_2, \dots, a_n (1 \le a_i \le 3) — кількість пінгвінів у -тій родині.

Вихідні дані

Виведіть цілих чисел — t_1, t_2, \dots, t_n з 1 \le t_i \le k, що позначають номер команди -ї родини так, щоб всі розміри команд були якомога ближчими.

Приклади

Приклад 1

Loading
Loading

Приклад 2

Loading
Loading

Приклад 3

Loading
Loading

Примітка

У першому прикладі розміри команд становлять (2+2), (1+3) та (1+3) відповідно; отже, всі розміри команд рівні, і таким чином розподіл є оптимальним.

У другому прикладі розміри становлять (2+3)=5 та (1+2+3)=6 з різницею . Можна показати, що неможливо сформувати дві команди з різницею розміру, що дорівнює .

У третьому прикладі розміри команд становлять (3), (3+2)=5, (3+3)=6 з різницею . Можна показати, що неможливо сформувати команди з різницею розміру менше ніж .