Prófessor Chen, virtur sérfræðingur í tölvustuddri fornletursfræði, hefur varið árum saman í að rannsaka handrit Óofgnóttar-keisaraættarinnar. Skrifarar þessa tímabils fylgdu sérkennilegri fagurfræðilegri kenningu: þeir trúðu því að texti glataði andlegum krafti sínum ef hann innihéldi „bergmál“.

Í þessu samhengi er stafaruglsbergmál (anagrammatic echo) skilgreint sem hvaða tveir ólíkir bútar texta sem er sem innihalda nákvæmlega sömu tákn í nákvæmlega sama magni, þótt röð þeirra sé ekki endilega sú sama. Fyrir texta sem táknuð er sem runa af táknum er bergmál til staðar ef til eru tveir ólíkir upphafsstaðir $x$ og $y$ þannig að hlutrunan af lengd $l$ sem byrjar í $x$ sé umröðun á hlutrununni af lengd $l$ sem byrjar í $y$. Skoðum til dæmis rununa $[1, 2, 1, 1, 3, 1, 2, 1]$. Búturinn af lengd $4$ sem byrjar í öðru sæti, $[2, 1, 1, 3]$, og búturinn af lengd $4$ sem byrjar í fimmta sæti, $[3, 1, 2, 1]$, mynda stafaruglsbergmál.

Prófessor Chen hefur grafið upp nokkrar slíkar bókrollur, en mörg tákn hafadofnað í tímans rás og skilið eftir eyður (táknaðar með $0$). Verkefni þitt er að fylla í þessar eyður með táknum úr leyfða menginu $\{1, 2, \dots, k\}$ þannig að Ósamhljómsstig (Dissonance Score) bókrollunnar verði sem minnst. Ósamhljómsstigið er mesta lengd $l$ á nokkru stafaruglsbergmáli sem kemur fyrir í útfylltu rununni.

Inntak

Það eru mörg prófunartilvik. Fyrsta línan í inntakinu inniheldur heiltölu $T$ ($1 \le T \le 10^4$) sem gefur til kynna fjölda prófunartilvika. Fyrir hvert prófunartilvik:

Fyrsta línan inniheldur tvær heiltölur $n$ og $k$ ($2 \le n \le 2 \times 10^5$, $1 \le k \le n$).

Önnur línan inniheldur $n$ heiltölur $a_1, a_2, \dots, a_n$ ($0 \le a_i \le k$).

Tryggt er að summa $n$ yfir öll prófunartilvik fari ekki yfir $2 \times 10^5$.

Úttak

Fyrir hvert prófunartilvik skal prenta $n$ heiltölur $b_1, b_2, \dots, b_n$ ($1 \le b_i \le k$) sem tákna endurheimtu rununa. Runan $b$ verður að stemma við $a$ í öllum sætum þar sem $a_i \neq 0$, og hún verður að ná lægsta mögulega Ósamhljómsstigi.

Ef fleiri en ein leið er til að endurheimta bókrolluna ákjósanlega mun prófessor Chen samþykkja hvaða leið sem er.

Dæmi

Inntak

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

Úttak

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