---
title: Palikat
---

Sinulla on rivissä $n$ palikkaa, joilla on $k$ eri väriä. Palikoiden värit ovat $c_1, c_2, \dots, c_n$ niin, että jokainen väri on välillä $1$ ja $k$.

Väri on _tasapainossa_, jos kyseisen väristen palikoiden kohtien keskiarvo on $(n+1)/2$. Huomaa, että tämä luku ei välttämättä ole kokonaisluku.

![Palikat väreillä 1, 2, 2, 1, 3, 1, 2](files/blocks.svg "=440x")

Esimerkiksi jos $7$ palikkaa on järjestetty yllä olevalla tavalla, värin $1$ kohtien keskiarvo on $(1 + 4 + 6) / 3 = \frac{11}{3}$, värin $2$ kohtien keskiarvo on $(2 + 3 + 7) / 3 = 4$ ja värin $3$ kohtien keskiarvo on $5$. Koska $(7+1)/2=4$, väri $2$ on tasapainossa mutta värit $1$ ja $3$ eivät ole.

Pystytkö järjestämään palikat niin, että kaikki värit ovat tasapainossa?

# Syöte

Ensimmäisellä rivillä on kokonaisluku $t$: testitapausten määrä.

Seuraavat rivit kuvaavat testitapaukset, joista jokainen muodostuu kahdesta rivistä seuraavasti:

Ensimmäisellä rivillä on kaksi kokonaislukua $n$ ja $k$: palikoiden määrä ja eri värien määrä.

Toisella rivillä on palikoiden värit $c_1, c_2, \dots, c_n$. Jokaista väriä on ainakin yksi palikka.

# Tuloste

Tulosta kussakin testitapauksessa "`YES`", jos ratkaisu on olemassa, ja "`NO`" muuten. Jos ratkaisu on olemassa, esitä yksi mahdollinen järjestys tulostamalla toiselle riville $n$ kokonaislukua: kussakin kohdassa olevan palikan väri.

# Rajat

- $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$
- Kaikkien $n$-arvojen summa on enintään $2 \cdot 10^5$

# Esimerkki

Syöte:
```
3
7 2
1 1 1 1 2 2 2
2 2
1 2
2 1
1 1
```

Tuloste:
```
YES
1 2 2 1 1 1 2
NO
YES
1 1
```

_Selitys_: Ensimmäisessä testitapauksessa väri $1$ on tasapainossa, koska kohtien keskiarvo on $(1 + 4 + 5 + 6) / 4 = 4$, joka on sama kuin $(n + 1) / 2$. Vastaavasti värin $2$ kohtien keskiarvo on $(2 + 3 + 7) / 3 = 4$. Molemmat värit ovat siis tasapainossa.

Toisessa testitapauksessa kumpikaan kahdesta mahdollisesta järjestyksestä ei tasapainota värejä.

Kolmannessa testitapauksessa värin $1$ palikat ovat kohdissa $1$ ja $2$. Keskiarvo on $3/2$, joten väri $1$ on tasapainossa.

# Pisteytys

| Osatehtävä | Rajoitukset | Pisteet    |
| :-----: | ----------- | :-------: |
| 1       | $n \le 3$   | [score=1] |
| 2       | $n \le 15$  | [score=2] |
| 3       | Enintään yksi väreistä esiintyy parittoman määrän kertoja | [score=3] |
| 4       | Jokainen väri esiintyy saman määrän kertoja | [score=4] |
| 5       | $k \le 15$  | [score=5] |
| 6       | Ei lisärajoituksia | [score=6] |
