---
title: Kubbar
---

Þú ert með $n$ viðar kubba í $k$ mismunandi litum. Kubbarnir eru raðaðir í línu. Litirnir kubbanna eru tölurnar $c_1, c_2, \dots, c_n$, allar milli $1$ og $k$.

Litur er sagður vera _jafnvægur_ ef meðalstaðsetning kubbanna er $(n+1)/2$. Takið eftir því að þessi tala er ekki endilega heiltala.

![Kubbar með liti 1, 2, 2, 1, 3, 1, 2](files/blocks.svg "=440x")

Til dæmis, ef $7$ kubbar eru raðaðir eins og hér að ofan þá er meðalstaðsetning lits $1$ er $(1 + 4 + 6) / 3 = 11/3$, meðalstaðsetning lits $2$ er $(2 + 3 + 7) / 3 = 4$ og meðalstaðsetning lits $3$ er $5$. Þar sem $(7+1)/2=4$ er litur $2$ er jafnvægur en litirnir $1$ og $3$ eru það ekki.

Getur þú raðað kubbunum þannig að allir litir eru jafnvægir?

# Intak

Fyrsta lína inniheldur eina tölu $t$: fjöldi prófunartilvika.

Næstu línur skilgreyna prófunartilvikin. Hvert prófunartilvik samanstendur úr tveim línum:

Fyrsta lína inniheldur tvær heiltölur $n$ og $k$: fjöldi kubba og fjöldi mismunandi lita.

Önnur lína inniheldur litina sem kubbarnir eru litaðir í $c_1, c_2, \dots, c_n$. Það er að minsta kosti einn kubbur í hverjum lit.

# Úttak

Fyrir hvert prófunartilvik, prentið "`YES`" ef lausn er til, og "`NO`" ef ekki. Ef lausn er til, lýsið einni mögulegri röðun kubba með því að prenta út $n$ heiltölur í annari línu: litina hvers kubs í röð.

# Takmarkanir

- $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$
- Summa alla $n$ er í mesta lagi $2 \cdot 10^5$

# Dæmi

Intak:
```
3
7 2
1 1 1 1 2 2 2
2 2
1 2
2 1
1 1
```

Úttak:
```
YES
1 2 2 1 1 1 2
NO
YES
1 1
```

_Útskíring_: Í úttaki fyrsta prófunartilviks, litur $1$ er jafnvægur þar sem meðalstaðsetningin hans er $(1 + 4 + 5 + 6) / 4 = 4$, sem er jafnt $(n + 1) / 2$. Á sama hátt, meðalstaðsetning lits $2$ er $(2 + 3 + 7) / 3 = 4$. Því eru báðir litirnir jafnvægir.

Í öðru prófunartilviki, hvorugt tveggja raða gerir litina jafnvæga.

Í úttaki þriðja prófunartilviks, kubbar með litinn $1$ eru á stöðum $1$ og $2$. Þar sem meðalstaðsetningin er $3/2$ er litur $1$ jafnvægur.

# Stigagjöf

| Hópur | Takmarkanir | Stig |
| :-----: | ----------- | :-------: |
| 1       | $n \le 3$   | [score=1] |
| 2       | $n \le 15$  | [score=2] |
| 3       | Það er í mesta lagi einn litur sem odda fjöldi kubba er litaður í | [score=3] |
| 4       | Allir litir birtast jafnoft | [score=4] |
| 5       | $k \le 15$  | [score=5] |
| 6       | Engar frekari takmarkanir | [score=6] |
