Professori Chen, laskennallisen paleografian arvostettu asiantuntija, on tutkinut vuosien ajan Ei-redundantin dynastian kirjoituksia. Tämän aikakauden kirjurit noudattivat erikoista esteettistä oppia: he uskoivat, että teksti menettää hengellisen voimansa, jos se sisältää ”kaikuja”.

Tässä yhteydessä anagramminen kaiku määritellään miksi tahansa kahdeksi tekstin eri jaksoksi, jotka – vaikka eivät välttämättä ole järjestykseltään identtisiä – sisältävät täsmälleen samoja symboleja täsmälleen yhtä monta kappaletta. Symbolijonona esitetylle tekstille kaiku on olemassa, jos on olemassa kaksi eri aloituskohtaa $x$ ja $y$ siten, että kohdasta $x$ alkava pituuden $l$ osataulukko on kohdasta $y$ alkavan pituuden $l$ osataulukon permutaatio. Tarkastellaan esimerkiksi jonoa $[1, 2, 1, 1, 3, 1, 2, 1]$. Toisesta kohdasta alkava pituuden $4$ jakso $[2, 1, 1, 3]$ ja viidennestä kohdasta alkava pituuden $4$ jakso $[3, 1, 2, 1]$ muodostavat anagrammisen kaiun.

Professori Chen on kaivanut esiin useita tällaisia kääröjä, mutta monet symbolit ovat haalistuneet ajan myötä jättäen aukkoja (joita merkitään luvulla $0$). Tehtäväsi on täyttää nämä aukot sallitun joukon $\{1, 2, \dots, k\}$ symboleilla siten, että käärön lopullinen riitasointupistemäärä (Dissonance Score) minimoituu. Riitasointupistemäärä on täydennetyssä jonossa esiintyvän anagrammisen kaiun suurin pituus $l$.

Syöte

Syötteessä on useita testitapauksia. Syötteen ensimmäinen rivi sisältää kokonaisluvun $T$ ($1 \le T \le 10^4$), joka ilmoittaa testitapausten lukumäärän. Jokaisessa testitapauksessa:

Ensimmäinen rivi sisältää kaksi kokonaislukua $n$ ja $k$ ($2 \le n \le 2 \times 10^5$, $1 \le k \le n$).

Toinen rivi sisältää $n$ kokonaislukua $a_1, a_2, \dots, a_n$ ($0 \le a_i \le k$).

On taattu, että lukujen $n$ summa yli kaikkien testitapausten ei ylitä arvoa $2 \times 10^5$.

Tuloste

Tulosta jokaista testitapausta kohden $n$ kokonaislukua $b_1, b_2, \dots, b_n$ ($1 \le b_i \le k$), jotka esittävät ennallistettua jonoa. Jonon $b$ täytyy täsmätä jonoon $a$ kaikissa kohdissa, joissa $a_i \neq 0$, ja sen täytyy saavuttaa pienin mahdollinen riitasointupistemäärä.

Jos käärön optimaaliseen ennallistamiseen on useita tapoja, professori Chen hyväksyy minkä tahansa niistä.

Esimerkki

Syöte

4
8 3
0 1 0 2 1 3 0 2
3 3
1 0 2
9 7
0 1 1 0 5 0 4 0 7
6 6
0 0 0 0 0 0

Tuloste

1 1 3 2 1 3 2 2
1 3 2
2 1 1 3 5 6 4 4 7
1 2 3 4 5 6