---
title: Klocki
---

Dane jest $n$ drewnianych klocków w $k$ różnych kolorach ułożonych w ciąg. Kolory klocków to kolejno $c_1, c_2 \dots, c_n$, przy czym każdy kolor mieści się w przedziale od $1$ do $k$.

Kolor nazywamy _zrównoważonym_, jeżeli średnia arytmetyczna pozycji klocków tego kolory wynosi $(n+1)/2$. Zwróć uwagę, że wartość ta nie musi być liczbą całkowitą.

![Klocki z kolorami 1, 2, 2, 1, 3, 1, 2](files/blocks.svg "=440x")

Dla przykładu, jeśli $7$ klocków jest ułożonych w powyższy sposób, średnia pozycja koloru $1$ wynosi $(1+4+6)/3 = 11/3$, średnia pozycja koloru $2$ wynosi $(2+3+7)/3=4$, a średnia pozycja koloru $3$ wynosi $5$. Ponieważ $(7+1)/2=4$, kolor $2$ jest zrównoważony, natomiast kolory $1$ i $3$ nie są.

Czy potrafisz ustawić klocki w taki sposób, aby wszystkie kolory były zrównoważone?

# Wejście

Pierwszy wiersz wejścia zawiera jedną liczbę całkowitą $t$: liczbę zestawów danych.

Następne wiersze opisują zestawy danych. Każdy zestaw składa się z dwóch wierszy:

Pierwszy wiersz zawiera dwie liczby całkowite $n$ oraz $k$: liczbę klocków i liczbę różnych kolorów.

Drugi wiersz zawiera kolory klocków $c_1, c_2, \dots, c_n$. Każdy kolor występuje co najmniej raz.

# Wyjście

Dla każdego zestawu danych wypisz "`YES`", jeśli rozwiązanie istnieje, lub "`NO`" w przeciwnym razie. Jeśli rozwiązanie istnieje, w kolejnym wierszu opisz przykładowe ustawienie, wypisując $n$ liczb całkowitych: kolory klocków na kolejnych pozycjach.

# Ograniczenia

- $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$
- Suma wartości $n$ po wszystkich zestawach danych nie przekracza $2 \cdot 10^5$

# Przykład

Wejście:
```
3
7 2
1 1 1 1 2 2 2
2 2
1 2
2 1
1 1
```

Wyjście:
```
YES
1 2 2 1 1 1 2
NO
YES
1 1
```

_Wyjaśnienie_: W wyjściu dla pierwszego zestawu kolor $1$ jest zrównoważony, ponieważ jego średnia pozycja to $(1 + 4 + 5 + 6) / 4 = 4$, co jest równe $(n + 1) / 2$. Podobnie średnia pozycja koloru $2$ wynosi $(2 + 3 + 7) / 3 = 4$. Oba kolory są zatem zrównoważone.

W drugim zestawie żadne z dwóch możliwych ustawień nie sprawia, że kolory są zrównoważone.

W wyjściu dla trzeciego zestawu klocki o kolorze $1$ znajdują się na pozycjach $1$ i $2$. Średnia wynosi $3/2$, więc kolor $1$ jest zrównoważony.

# Ocenianie

| Podzadanie | Ograniczenia | Punkty    |
| :-----: | ----------- | :-------: |
| 1       | $n \le 3$   | [score=1] |
| 2       | $n \le 15$  | [score=2] |
| 3       | Co najwyżej jeden kolor występuje nieparzystą liczbę razy | [score=3] |
| 4       | Wszystkie kolory występują tę samą liczbę razy | [score=4] |
| 5       | $k \le 15$  | [score=5] |
| 6       | Brak dodatkowych ograniczeń | [score=6] |
