---
title: Klotsid
---

Sul on ühes reas $n$ puidust klotsi, mis on värvitud $k$ eri värviga.
Klotside värvid on $c_1, c_2, \dots, c_n$, kõik vahemikus $1$ kuni $k$.

Värv on _tasakaalus_, kui seda värvi klotside keskmine kohanumber on $(n+1)/2$. Pane tähele, et see ei ole tingimata täisarv.

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

Näiteks, kui $7$ klotsi on järjestatud nii, nagu üleval toodud, siis on värvi $1$ keskmine kohanumber $(1 + 4 + 6) / 3 = 11/3$, värvi $2$ keskmine kohanumber on $(2 + 3 + 7) / 3 = 4$ ja värvi $3$ keskmine kohanumber on $5$. Kuna $(7+1)/2=4$, siis värv $2$ on tasakaalus, kuid värvid $1$ ja $3$ ei ole.

Kas saad järjestada klotsid nii, et kõik värvid on tasakaalus?

# Sisend

Esimesel real on üks täisarv $t$: testjuhtude arv.

Järgmised read kirjeldavad testjuhtusid. Iga testjuht koosneb kahest reast:

Esimesel real on kaks täisarvu $n$ ja $k$: klotside arv ja erinevate värvide arv.

Teisel real on klotside värvid $c_1, c_2, \dots, c_n$. Igast värvist on vähemalt üks klots.

# Väljund

Iga testjuhu jaoks väljasta "`YES`", kui sobiv järjestus leidub, vastasel juhul väljasta "`NO`". Kui sobiv järjestus leidub, siis too näide ühest võimalikust järjestusest, väljastades järgmisel real $n$ arvu: iga klotsi värv. 

# Piirangud

- $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$
- Kõigi $n$ väärtuste summa on maksimaalselt $2 \cdot 10^5$

# Näide

Sisend:
```
3
7 2
1 1 1 1 2 2 2
2 2
1 2
2 1
1 1
```

Väljund:
```
YES
1 2 2 1 1 1 2
NO
YES
1 1
```

_Selgitus_: Esimese testjuhu väljundis on värv $1$ on tasakaalus, sest selle keskmine kohanumber on $(1 + 4 + 5 + 6) / 4 = 4$, mis on võrdne arvuga $(n + 1) / 2$. Sarnaselt on värvi $2$ keskmine kohanumber $(2 + 3 + 7) / 3 = 4$. Mõlemad värvid on seega tasakaalus.

Teises testjuhus pole kummagi kahe võimaliku järjestuse korral värvid tasakaalus.

Kolmanda testjuhu väljundis on värviga $1$ klotsid asukohtadel $1$ ja $2$. Keskmine on $3/2$, seega värv $1$ on tasakaalus.

# Hindamine

| Grupp | Piirangud | Punkte    |
| :-----: | ----------- | :-------: |
| 1       | $n \le 3$   | [score=1] |
| 2       | $n \le 15$  | [score=2] |
| 3       | On ülimalt üks värv, mis esineb paaritu arvu kordi | [score=3] |
| 4       | Kõik värvid esinevad võrdse arvu kordi | [score=4] |
| 5       | $k \le 15$  | [score=5] |
| 6       | Lisapiirangud puuduvad | [score=6] |
