Il professor Chen, illustre esperto di Paleografia Computazionale, ha trascorso anni a studiare i manoscritti della dinastia Non-Ridondante. Gli scribi di quell'epoca seguivano una peculiare dottrina estetica: credevano che un testo perdesse la sua potenza spirituale se conteneva degli "echi".
In questo contesto, un eco anagrammatico è definito come una coppia di segmenti distinti di un testo che, pur non essendo necessariamente identici nell'ordine, contengono esattamente gli stessi simboli nelle stesse identiche quantità. Per un testo rappresentato come una sequenza di simboli, esiste un eco se ci sono due diverse posizioni di partenza $x$ e $y$ tali che il sottoarray di lunghezza $l$ che inizia in $x$ sia una permutazione del sottoarray di lunghezza $l$ che inizia in $y$. Ad esempio, si consideri la sequenza $[1, 2, 1, 1, 3, 1, 2, 1]$. Il segmento di lunghezza $4$ che inizia alla seconda posizione, $[2, 1, 1, 3]$, e il segmento di lunghezza $4$ che inizia alla quinta posizione, $[3, 1, 2, 1]$, formano un eco anagrammatico.
Il professor Chen ha riportato alla luce diversi rotoli di questo tipo, ma molti simboli sono sbiaditi nel tempo, lasciando delle lacune (rappresentate da $0$). Il tuo compito è riempire queste lacune utilizzando i simboli dell'insieme consentito $\{1, 2, \dots, k\}$ in modo da minimizzare il Punteggio di Dissonanza (Dissonance Score) risultante del rotolo. Il Punteggio di Dissonanza è la lunghezza massima $l$ di qualsiasi eco anagrammatico presente nella sequenza completata.
Input
Ci sono più casi di test. La prima riga dell'input contiene un intero $T$ ($1 \le T \le 10^4$) che indica il numero di casi di test. Per ciascun caso di test:
La prima riga contiene due interi $n$ e $k$ ($2 \le n \le 2 \times 10^5$, $1 \le k \le n$).
La seconda riga contiene $n$ interi $a_1, a_2, \dots, a_n$ ($0 \le a_i \le k$).
È garantito che la somma di $n$ su tutti i casi di test non superi $2 \times 10^5$.
Output
Per ciascun caso di test, stampa $n$ interi $b_1, b_2, \dots, b_n$ ($1 \le b_i \le k$) che rappresentano la sequenza restaurata. La sequenza $b$ deve coincidere con $a$ in tutte le posizioni in cui $a_i \neq 0$ e deve ottenere il minimo Punteggio di Dissonanza possibile.
Se esistono più modi per restaurare il rotolo in modo ottimale, il professor Chen accetterà uno qualsiasi di essi.
Esempio
Input
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
Output
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