---
title: Блоки
---

У вас є $n$ дерев’яних блоків $k$ різних кольорів, розташованих у ряд. Кольори блоків задані як $c_1, c_2, \dots, c_n$, кожен у межах від $1$ до $k$.

Колір називається _збалансованим_, якщо середня позиція блоків цього кольору дорівнює $(n+1)/2$. Зауважте, що це значення не обов’язково є цілим числом.

![Blocks with colors 1, 2, 2, 1, 3, 1, 2](files/blocks.svg "=440x")

Наприклад, якщо $7$ блоків розташовані, як показано вище, середня позиція кольору $1$ дорівнює $(1 + 4 + 6) / 3 = 11/3$, середня позиція кольору $2$ дорівнює $(2 + 3 + 7) / 3 = 4$, а середня позиція кольору $3$ дорівнює $5$. Оскільки $(7+1)/2=4$, колір $2$ є збалансованим, а кольори $1$ і $3$ — ні.

Чи можете ви впорядкувати блоки так, щоб усі кольори були збалансованими?

# Вхідні дані

Перший рядок містить одне ціле число $t$: кількість тестових випадків.

Наступні рядки описують тестові випадки, кожен із яких складається з двох рядків:

Перший рядок містить два цілі числа $n$ і $k$: кількість блоків і кількість різних кольорів.

Другий рядок містить кольори блоків $c_1, c_2, \dots, c_n$. Гарантується, що кожен колір зустрічається хоча б один раз.

# Вихідні дані

Для кожного тестового випадку виведіть "`YES`", якщо розв’язок існує, і "`NO`" — якщо ні. Якщо розв’язок існує, виведіть один можливий порядок, надрукувавши $n$ цілих чисел у наступному рядку: колір блоку на кожній позиції.

# Обмеження

- $1 \le t \le 100$
- $1 \le k \le n \le 2 \cdot 10^5$
- $1 \le c_1, c_2, \dots, c_n \le k$
- Сума всіх $n$ не перевищує $2 \cdot 10^5$

# Приклад

Вхідні дані:
```
3
7 2
1 1 1 1 2 2 2
2 2
1 2
2 1
1 1
```

Вихідні дані:
```
YES
1 2 2 1 1 1 2
NO
YES
1 1
```

_Пояснення_: У відповіді для першого тестового випадку колір $1$ є збалансованим, оскільки його середня позиція дорівнює $(1 + 4 + 5 + 6) / 4 = 4$, що дорівнює $(n + 1) / 2$. Аналогічно, середня позиція кольору $2$ дорівнює $(2 + 3 + 7) / 3 = 4$. Отже, обидва кольори є збалансованими.

У другому тестовому випадку жоден із двох можливих порядків не робить кольори збалансованими.

У відповіді для третього тестового випадку блоки кольору $1$ розташовані на позиціях $1$ і $2$. Середнє дорівнює $3/2$, отже колір $1$ є збалансованим.

# Оцінювання

| Підзадача | Обмеження | Бали    |
| :-----: | ----------- | :-------: |
| 1       | $n \le 3$   | [score=1] |
| 2       | $n \le 15$  | [score=2] |
| 3       | Існує не більше одного кольору, який зустрічається непарну кількість разів | [score=3] |
| 4       | Усі кольори зустрічаються однакову кількість разів | [score=4] |
| 5       | $k \le 15$  | [score=5] |
| 6       | Без додаткових обмежень | [score=6] |
